Algorithmes haute résolution linéaires pour l’estimation des temps de retard dans un contexte de bruit quelconque - Linear high-resolution algorithms for time delay estimation in the case of an arbitrary noise

The high-resolution spectral analysis methods such as MUSIC and ESPRIT have been proposed in the eighties to improve the resolution capability of the conventional spectral analysis methods (FFT). They are based on the eigendecomposition of the data covariance matrix and could be used either for pure frequency, direction-of-arrival (DOA) or time delay estimations (TDE). In the nineties, the subspace methods called « Linear» such as BEWE, PM and SWEDE have been proposed. They only use linear operations on the data and do not require the costly eigendecomposition of the covariance matrix. They are better suited to process large data size or to perform real time applications. These methods have been especially developed in array signal processing.

This paper focuses on the linear high resolution SWEDE algorithm by Eriksson et al., because, on one hand, its principle is a generalization of the PM and BEWE algorithms, and on the other hand, this method allows to develop linear versions of the ESPRIT method in the case of an arbitrary noise.

In this paper, two improvements of the SWEDE algorithm are proposed for estimating the time delays within a signal with an arbitrary noise.

The received signal is composed of the sum of K backscattered echoes from each interface. Each echo is a time shifted copy of the emitted radar pulse e(t). Then, the received signal can be written as indicated in (1). In the frequency domain, the received signal is a linear combination of cisoids modulated by the radar pulse e˜(f). This frequency form is suitable to perform the time delays estimation with spectral analysis techniques. For N discrete frequencies within the bandwidth B, the received signal is written in the matrix form as shown in (3), where Λ is the diagonal matrix whose diagonal elements are the Fourier Transform e˜(f) of the radar pulse e(t). Thereafter, the covariance matrices of the data vector are written as indicated in (4).

At first, the SWEDE algorithm is adapted to TDE by taking into account the shape of the radar pulse e˜(f) in the mathematical formulation. The SWEDE algorithm is based on the partitioning of the mode matrix A into three sub-matrices (5). When we take into account the radar pulse in the SWEDE method, the principle consists in partitioning the matrix Λ into three sub-matrices Λ1, 2, 3 as shown in section 3. Then, the orthonormal projector is calculated and defined in equation (13). The time delays are found by searching the maximum of the cost function or pseudo-spectrum defined in equation (14). The orthonormal projector is obtained from three off-diagonal blocks of the observation covariance matrix, Γ12,Γ13 and Γ23. Therefore, the SWEDE method is not disturbed if the noise covariance matrix is block-diagonal. In the general case when the noise covariance matrix Σ is any positive-definite hermitian matrix, SWEDE requires a preliminary whitening which consists in multiplying the data vector r by the matrix Σ-1/2, such as y = Σ-1/2r. This method requires a great number of operations (i.e. about N2) and implies a computational burden too important for real time applications.

To reduce the computational burden, Eriksson et al. have proposed a noise whitening technique which only requires O(NK) arithmetic operations. The data r are then multiplied by the matrix Q defined in equation (19). The new noise covariance matrix Σw after whitening shows a non null off-diagonal block element Σ12 which may result in a biased time delay estimation.

To overcome this drawback in the case of an arbitrary noise, two improvements of the linear high resolution algorithm SWEDE are proposed for estimating the time delays. The first one aims at improving the original noise whitening technique proposed by Eriksson et al.. We propose to use a new whitening method allowing the Full Block Diagonalization of the noise covariance matrix. This new whitening method combined with the SWEDE algorithm gives the new method called FBD-SWEDE for Full Block Diagonalization-SWEDE. FBD-SWEDE uses the new matrix Q defined in equation (24) and allows to cancel out the off-diagonal block element Σw 12. In a context of an arbitrary noise, the SWEDE algorithm can then be applied to these new preprocessed data and achieve unbiased estimation.

In pratice, the estimation of time delays is deduced from the positions of the maxima in the pseudo-spectrum. Due to its extensive dynamic range, a high sampling rate is required to accurately describe the pseudospectrum variations and to locate the positions of the maxima. This last step of the algorithm increases substantially the computational time.

In the case of an arbitrary noise, the second proposition consists in using ESPRIT in combination with SWEDE in order to make the estimation more efficient. Thus, we obtain a new algorithm called FBD-G-ESPRITWED for Full Block Diagonalization-Generalized-ESPRIT Without Eigen Decomposition. In comparison with the conventional ESPRIT algorithm, FBD-G-ESPRITWED does not require the eigendecomposition of the data covariance matrix, but needs the eigenvalues of the K × K similar matrix H. Besides, in comparison with SWEDE, FBD-G-ESPRITWED does not require the pseudo-spectrum calculation, it allows a direct estimation of time delays. The principle of FBD-G-ESPRITWED is based on, on one hand, the equations (35)-(37) and the diagonal matrix Φ, and on the other hand, on the noise whitening method proposed in the FBD-SWEDE method. As for the ESPRIT algorithm, the time delays can be estimated directly from the diagonal elements of the matrix Φ. However, the matrix Φ is not estimated directly from the data. The principle is to retrieve the phase shifts of Φ from the off-diagonal block matrices of the data covariance matrix as shown in the equations (37) to (42). In the case of an arbitrary noise, the data are firstly multiplied by the matrix Q defined in equation (24). Thus, the three off-diagonal block matrices Γw 12, Γw 13, Γw 23 of the modified data covariance matrix are not affected by the noise. Then, the matrices Y, H are estimated from eqn. (42) and (41) respectively. The K first eigenvalues of the matrix H are then calculated and the time delays are estimated from the arguments of the eigenvalues of H. In comparison with the SWEDE algorithm, FBD-G-ESPRITWED is optimal. The proposed method is based on the two block elements of the modified data covariance matrix (Γw 13, Γw 23) which are not affected by the noise.

To assess the performance of the proposed algorithms, FBD-SWEDE and FBD-G-ESPRITWED are compared with the conventional SWEDE algorithm. They are tested on simulated data to measure the layer thickness of civil engineering materials. The simulated data obey to the model in eqn. (3). The power of the two sources are fixed to 0 and –6 dB respectively. The performance is established with a Monte Carlo process which consists of 500 independent runs of the algorithms. For each run, the correlation matrix is estimated from M = 200 independent snapshots, from which the various algorithms perform the estimation of the thickness and the failure test. The generated noise is correlated, resulting in a non diagonal covariance matrix. Figures (1), (2) and (3) show the failure rate and the standard deviation on the estimated thickness with regards to the SNR, for the three algorithms: SWEDE, FBD-SWEDE and FBD-G-ESPRITWED. As expected, the performance improves with increasing SNR. Figures (4) and (5) show how the B ∆ τ product affects the performance of the algorithms at medium SNR (20 dB). The performance also improves with increasing B ∆ τ. The simulations show that FBD-G-ESPRITWED has the best resolution power and the best noise robustness.

However, FBD-SWEDE shows the smallest standard deviation. The results show that FBD-SWEDE has the best trade-offbetween the resolution power and the accuracy on thickness estimation. In practice, according to the requirements of the radar application, the user may prefer FBD-G-ESPRITWED to achieve the best resolution capability, or FBD-SWEDE to obtain the best accuracy on the thickness estimation. Finally, this article shows that the time resolution of the two proposed methods is better than that of the initial linear subspace method, SWEDE.

Résumé

Cet article propose quelques améliorations de l’algorithme haute résolution linéaire SWEDE pour l’estimation de retards de propagation dans un contexte de bruit quelconque. La première amélioration consiste à modifier

le procédé initial de blanchiment du bruit proposé par Eriksson et al. La nouvelle méthode ainsi obtenue est appelée FBD-SWEDE pour Full Block Diagonalization-SWEDE. La seconde amélioration introduit l’algorithme ESPRIT dans le formalisme de SWEDE, réduisant ainsi le temps de calcul. Nous appelons cette méthode FBD-G-ESPRITWED pour Full Block Diagonalization-Generalized-ESPRIT Without Eigen Decomposition. Les résultats de simulation concernent la mesure d’épaisseur de matériaux de génie civil à l’aide d’un radar en ondes centimétriques. Ils montrent que la résolution temporelle des deux méthodes proposées es supérieure à celle de la méthode HR linéaire initiale, SWEDE.