MUSIC (MUltiple SIgnal Classification) is an algorithm used for frequency estimation[1][2][3] and radio direction finding.[4]

The radio direction finding by the MUSIC algorithm

History

edit

In many practical signal processing problems, the objective is to estimate from measurements a set of constant parameters upon which the received signals depend. There have been several approaches to such problems including the so-called maximum likelihood (ML) method of Capon (1969) and Burg's maximum entropy (ME) method. Although often successful and widely used, these methods have certain fundamental limitations (especially bias and sensitivity in parameter estimates), largely because they use an incorrect model (e.g., AR rather than special ARMA) of the measurements.

Pisarenko (1973) was one of the first to exploit the structure of the data model, doing so in the context of estimation of parameters of complex sinusoids in additive noise using a covariance approach. Schmidt (1977), while working at Northrop Grumman and independently Bienvenu and Kopp (1979) were the first to correctly exploit the measurement model in the case of sensor arrays of arbitrary form. Schmidt, in particular, accomplished this by first deriving a complete geometric solution in the absence of noise, then cleverly extending the geometric concepts to obtain a reasonable approximate solution in the presence of noise. The resulting algorithm was called MUSIC (MUltiple SIgnal Classification) and has been widely studied.

In a detailed evaluation based on thousands of simulations, the Massachusetts Institute of Technology's Lincoln Laboratory concluded in 1998 that, among currently accepted high-resolution algorithms, MUSIC was the most promising and a leading candidate for further study and actual hardware implementation.[5] However, although the performance advantages of MUSIC are substantial, they are achieved at a cost in computation (searching over parameter space) and storage (of array calibration data).[6]

Theory

edit

MUSIC method assumes that a signal vector,  , consists of   complex exponentials, whose frequencies   are unknown, in the presence of Gaussian white noise,  , as given by the linear model

 

Here   is an   Vandermonde matrix of steering vectors   and   is the amplitude vector. A crucial assumption is that number of sources,  , is less than the number of elements in the measurement vector,  , i.e.  .

The   autocorrelation matrix of   is then given by

 

where   is the noise variance,   is   identity matrix, and   is the   autocorrelation matrix of  .

The autocorrelation matrix   is traditionally estimated using sample correlation matrix

 

where   is the number of vector observations and  . Given the estimate of  , MUSIC estimates the frequency content of the signal or autocorrelation matrix using an eigenspace method.

Since   is a Hermitian matrix, all of its   eigenvectors   are orthogonal to each other. If the eigenvalues of   are sorted in decreasing order, the eigenvectors   corresponding to the   largest eigenvalues (i.e. directions of largest variability) span the signal subspace  . The remaining   eigenvectors correspond to eigenvalue equal to   and span the noise subspace  , which is orthogonal to the signal subspace,  .

Note that for  , MUSIC is identical to Pisarenko harmonic decomposition. The general idea behind MUSIC method is to use all the eigenvectors that span the noise subspace to improve the performance of the Pisarenko estimator.

Since any signal vector   that resides in the signal subspace   must be orthogonal to the noise subspace,  , it must be that   for all the eigenvectors   that spans the noise subspace. In order to measure the degree of orthogonality of   with respect to all the  , the MUSIC algorithm defines a squared norm

 

where the matrix   is the matrix of eigenvectors that span the noise subspace  . If  , then   as implied by the orthogonality condition. Taking a reciprocal of the squared norm expression creates sharp peaks at the signal frequencies. The frequency estimation function for MUSIC (or the pseudo-spectrum) is

 

where   are the noise eigenvectors and

 

is the candidate steering vector. The locations of the   largest peaks of the estimation function give the frequency estimates for the   signal components

 

MUSIC is a generalization of Pisarenko's method, and it reduces to Pisarenko's method when  . In Pisarenko's method, only a single eigenvector is used to form the denominator of the frequency estimation function; and the eigenvector is interpreted as a set of autoregressive coefficients, whose zeros can be found analytically or with polynomial root finding algorithms. In contrast, MUSIC assumes that several such functions have been added together, so zeros may not be present. Instead there are local minima, which can be located by computationally searching the estimation function for peaks.

Dimension of signal space

edit

The fundamental observation MUSIC and other subspace decomposition methods are based on is about the rank of the autocorrelation matrix   which is related to number of signal sources   as follows.

If the sources are complex, then   and the dimension of the signal subspace   is  . If sources are real, then   and dimension of the signal subspace is  , i.e. each real sinusoid is generated by two base vectors.

This fundamental result, although often skipped in spectral analysis books, is a reason why the input signal can be distributed into   signal subspace eigenvectors spanning   (  for real valued signals) and noise subspace eigenvectors spanning  . It is based on signal embedding theory [2] [7] and can also be explained by the topological theory of manifolds.[4]

Comparison to other methods

edit

MUSIC outperforms simple methods such as picking peaks of DFT spectra in the presence of noise, when the number of components is known in advance, because it exploits knowledge of this number to ignore the noise in its final report.

Unlike DFT, it is able to estimate frequencies with accuracy higher than one sample, because its estimation function can be evaluated for any frequency, not just those of DFT bins. This is a form of superresolution.

Its chief disadvantage is that it requires the number of components to be known in advance, so the original method cannot be used in more general cases. Methods exist for estimating the number of source components purely from statistical properties of the autocorrelation matrix. See, e.g. [8] In addition, MUSIC assumes coexistent sources to be uncorrelated, which limits its practical applications.

Recent iterative semi-parametric methods offer robust superresolution despite highly correlated sources, e.g., SAMV[9][10]

Other applications

edit

A modified version of MUSIC, denoted as Time-Reversal MUSIC (TR-MUSIC) has been recently applied to computational time-reversal imaging.[11][12] MUSIC algorithm has also been implemented for fast detection of the DTMF frequencies (Dual-tone multi-frequency signaling) in the form of C library - libmusic[13] (including for MATLAB implementation).[14]

See also

edit

References

edit
  1. ^ Hayes, Monson H., Statistical Digital Signal Processing and Modeling, John Wiley & Sons, Inc., 1996. ISBN 0-471-59431-8.
  2. ^ a b Gregor, Piotr (2022). Zastosowanie algorytmu MUSIC do wykrywania DTMF [Application of MUSIC algorithm to DTMF detection] (Thesis) (in Polish). Warsaw University of Technology.
  3. ^ Costanzo, Sandra; Buonanno, Giovanni; Solimene, Raffaele (2022). "Super-Resolution Spectral Approach for the Accuracy Enhancement of Biomedical Resonant Microwave Sensors". IEEE Journal of Electromagnetics, RF and Microwaves in Medicine and Biology. 6 (4): 539–545. doi:10.1109/JERM.2022.3210457. ISSN 2469-7249. S2CID 252792474.
  4. ^ a b Schmidt, R.O, "Multiple Emitter Location and Signal Parameter Estimation," IEEE Trans. Antennas Propagation, Vol. AP-34 (March 1986), pp. 276–280.
  5. ^ Barabell, A. J. (1998). "Performance Comparison of Superresolution Array Processing Algorithms. Revised" (PDF). Massachusetts Inst of Tech Lexington Lincoln Lab. Archived (PDF) from the original on May 25, 2021.
  6. ^ R. Roy and T. Kailath, "ESPRIT-estimation of signal parameters via rotational invariance techniques," in IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, no. 7, pp. 984–995, Jul 1989.
  7. ^ Penny, W. D. (2009), Signal Processing Course, University College London, Lecture notes 1999–2000 academic year
  8. ^ Fishler, Eran, and H. Vincent Poor. "Estimation of the number of sources in unbalanced arrays via information theoretic criteria." IEEE Transactions on Signal Processing 53.9 (2005): 3543–3553.
  9. ^ Abeida, Habti; Zhang, Qilin; Li, Jian; Merabtine, Nadjim (2013). "Iterative Sparse Asymptotic Minimum Variance Based Approaches for Array Processing". IEEE Transactions on Signal Processing. 61 (4). Institute of Electrical and Electronics Engineers (IEEE): 933–944. arXiv:1802.03070. Bibcode:2013ITSP...61..933A. doi:10.1109/tsp.2012.2231676. ISSN 1053-587X. S2CID 16276001.
  10. ^ Zhang, Qilin; Abeida, Habti; Xue, Ming; Rowe, William; Li, Jian (2012). "Fast implementation of sparse iterative covariance-based estimation for source localization". The Journal of the Acoustical Society of America. 131 (2): 1249–1259. Bibcode:2012ASAJ..131.1249Z. doi:10.1121/1.3672656. PMID 22352499.
  11. ^ Devaney, A.J. (2005-05-01). "Time reversal imaging of obscured targets from multistatic data". IEEE Transactions on Antennas and Propagation. 53 (5): 1600–1610. Bibcode:2005ITAP...53.1600D. doi:10.1109/TAP.2005.846723. ISSN 0018-926X. S2CID 25241225.
  12. ^ Ciuonzo, D.; Romano, G.; Solimene, R. (2015-05-01). "Performance Analysis of Time-Reversal MUSIC". IEEE Transactions on Signal Processing. 63 (10): 2650–2662. Bibcode:2015ITSP...63.2650C. doi:10.1109/TSP.2015.2417507. ISSN 1053-587X. S2CID 5895440.
  13. ^ "libmusic: A powerful C library for spectral analysis". Data and Signal. 2023.
  14. ^ "libmusic_m : MATLAB implementation". Data and Signal. 2023. MathWorks.

Further reading

edit
  • The estimation and tracking of frequency, Quinn and Hannan, Cambridge University Press 2001.