An Introduction to MUSIC and ESPRIT - GIRD Systems

1 An Introduction to MUSIC and ESPRIT . GIRD Systems , Inc. 310 Terrace Ave. Cincinnati, Ohio 45220. Based on R. O. Schmidt, Multiple emitter location and signal parameter estimation, . IEEE Trans. Antennas & Propagation, vol. 34, no. 3, March 1986, and R. Roy and T. Kailath, ESPRIT Estimation of signal parameters via rotation invariance techniques, IEEE Trans. Acoust., Speech, Signal Proc., vol. 17, no. 7, July 1989. Introduction Well known high-resolution DOA algorithms Able to find DOAs of multiple sources High spatial resolution compared with other alg. ( , a few antennas can result in high accuracy). MUSIC stands for Multiple Signal Classifier ESPRIT stands for Estimation of Signal Parameters via Rotational Invariance Technique Apply to only narrowband signal sources Narrowband Signal Sources A complex sinusoid s(t ) e j e j t e j t A real sinusoid is a sum of two sinusoids.

2 Cos( t ) j . e e j t e j e j t 1e j t 2e j t 2 2. A delay of a sinusoid is a phase shift s(t t0 ) e j t0 e j t e j t0 s(t ). Apply approximately to narrowband signals Narrowband Signal Sources Consider I narrowband signal sources s1 (t ) 1e j 1t , s2 (t ) 2e j 2t , , sI (t ) I e j I t Assume that all frequencies are different Assume that all amplitudes are uncorrelated i2 ; i j E{ i j } . 0; i j A Uniform Linear Array A signal source s(t ) e j t . impinges on the array with an angle . c: propagation speed If the received signal at sensor 1 is x1 (t ) s(t ). (i 1)d sin . Then it is delayed at sensor i by i . c Then the received signal at sensor i is ( i 1) d sin.

3 J . xi (t ) e j i s1 (t ) e j i s(t ) e c s(t ). Signal Model Put received signals at all N sensors together: 1 . x1 (t ) j d sin . x (t ) e c . 2 2 d sin .. x(t ) x3 (t ) e j c s(t ) a( ) s(t ).. xN (t ) . j ( N 1)cd sin . e . a( ) is called a steering vector . Signal Model If there are I sources signals received by the array, we get a signal model : x(t) --- received signal vector ( N by 1 ). s(t) --- source signal vector ( I by 1 ). n(t) --- noise vector ( N by 1 ). ( N by I ). s(t ) [ s1 (t ), , sI (t )]T. Sources are independent, noises are uncorrelated Column of A can also be normalized The MUSIC Algorithm Compute the N x N correlation matrix R x E{x(t )x H (t )} ARs A H 02I.

4 Where Rs E{s(t )s H (t )} diag.{ 12 , , I2 }. If the sources are somewhat correlated so R s is not diagonal, it will still work if R s has full rank. If the sources are correlated such that R s is rank deficient, then it is a problem. A common solution is spatial smoothing . Q: Why is the rank of R s (being I) so important? A: It defines the dimension of the signal subspace. The MUSIC Algorithm For N > I, the matrix ARs A H is singular, , det[ARs A H ] det[R x 02I] 0. But this implies that 02 is an eigenvalue of R x Since the dimension of the null space of ARs A H is N- I, there are N-I such eigenvalues 02 of R x Since both R x and ARs A H are non-negative definite, 2.

5 There are I other eigenvalues i such that i 2. 0 0. 2. Let u i be the ith eigenvector of R x corresponding to i 2. R xui [ARs A H 02I]ui i2ui ; i 1, 2, ,N. i2 02 0, i 1, , I ; i2 02 , i I 1, , N. The MUSIC Algorithm R xui [ARs A H 02I]ui i2ui ; i 1, 2, ,N. This implies ARs A H ui ( i2 02 )ui ; i 1, 2, ,N. ( 2. 2. 0 )ui ; i 1, 2, , I. AR s A ui . H i 0; i I 1, , N. Partition the N-dimensional vector space into the signal subspace U s and the noise subspace U n Us Un [ u1 uI u I 1 uN ]. Us : ( i2 02 ) 0 eigenvalues Un : 0 eigenvalues The MUSIC Algorithm The steering vector a( i ) is in the signal subspace Signal subspace is orthogonal to noise subspace ( i 0 )ui ; i 1, 2, , I (1).

6 2 2. AR s A ui . H. 0; i I 1, , N (2). (1) means I linear combinations of columns of A. equal the signal subspace spanned by columns of U s (2) means the linear combinations of columns of A, , the signal subspace, is orthogonal to U n The MUSIC Algorithm The steering vector a( i ) is in the signal subspace Signal subspace is orthogonal to noise subspace This implies that a H ( i )Un 0. So the MUSIC algorithm searches through all angles , and plots the spatial spectrum . 1. P( ) . a ( )Un H. Wherever i , P( ) exhibits a peak Peak detection will give spatial angles of all incident sources The MUSIC Algorithm MUSIC spatial spectrum compared with other methods Pros/Cons of The MUSIC Algorithm Works for other array shapes, need to know sensor positions Very sensitive to sensor position, gain, and phase errors.

7 Need careful calibration to make it work well Searching through all could be computationally expensive The ESPRIT algorithm overcomes such shortcomings to some degree ESPRIT relaxes the calibration task somewhat ESPRIT takes much less computation But ESPRIT takes twice as many sensors The ESPRIT Algorithm Based on doublets of sensors, , in each pair of sensors the two should be identical, and all doubles should line up completely in the same direction with a displacement vector having magnitude . Otherwise there are no restrictions, the sensor patterns could be very different from one pair to another The positions of the doublets are also arbitrary This makes calibration a little easier Assume N sets of doublets, , 2N sensors Assume I sources, N > I.

8 The ESPRIT Algorithm .. The amount of delay between two sensors in each doublet for a given incident signal is the same for all doublets, which is sin / c A sensor array of doublets The ESPRIT Algorithm This array is consisted of two identical subarrays, Z x and Z y , displaced from each other by . I. x(t ) a( i ) si (t ) n x (t ) As(t ) n x (t ). i 1. I. y (t ) a( i ) e si (t ) n x (t ) A s(t ) n x (t ). j i i 1. i 0 sin i / c diag.{e j 1 , e j 2 , , e j I }. The steering vector a( ) depends on the array geometry, and should be known just like in MUSIC . The ESPRIT Algorithm The objective is to estimate , thereby obtaining i Define x(t ) A n x (t ).

9 Z(t ) s(t ) As(t ) n z (t ). y (t ) A n y (t ) . Compute the 2N x 2N correlation matrix R z E{z(t )z H (t )} ARs A H 02I. Since there are I sources, the I eigenvectors of R z corresponding to the I largest eigenvalues form the signal subspace U s ; The remaining 2N-I. eigenvectors form the noise subspace U n The ESPRIT Algorithm U s is 2N x I, and its span is the same as the span of A. Therefore, there exists a unique nonsingular I x I. matrix T such that (A needs to be known here). Us AT. Partition U s into two N x I submatrices U x AT . Us . y . U A T . The columns of both U x and U y are linear combinations of A , so each of them has a column rank I.

10 The ESPRIT Algorithm Define an N x 2I matrix, which has rank I. Uxy U x U y . Therefore, U xy has a null space with dimension I, , there exists a 2I x I matrix F such that Fx . U xy F 0 U x U y U x Fx U y Fy 0. Fy . ATFx A TFy 0 A TFy ATFx Then the above gives, since T has full column rank A T ATFxFy 1 A ATFxFy 1T 1 TFxFy 1T 1. The ESPRIT Algorithm The final algorithm is 1 1. TF F T. x y In practice, the measurement could be noisy, and there could be array calibration errors, so a total least squares ESPRIT is used The estimation is one shot , even with matrix inversions the computation is much less than the MUSIC search We must have N > I for ESPRIT to work with 2N.