MUSIC (algorithm)
MUSIC (MUltiple SIgnal Classification) is an algorithm used for frequency estimation and radio direction finding. History. 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. 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). Theory. MUSIC method assumes that a signal vector, formula_1, consists of formula_2 complex exponentials , whose frequencies formula_3 are unknown, in the presence of Gaussian white noise, formula_4, as given by the linear model Here formula_6 is an formula_7 Vandermonde matrix of steering vectors formula_8 and formula_9 is the amplitude vector. A crucial assumption is that number of sources, formula_2, is less than the number of elements in the measurement vector, formula_11, i.e. formula_12. The formula_13 autocorrelation matrix of formula_1 is then given by where formula_16 is the noise variance, formula_17 is formula_13 identity matrix, and formula_19 is the formula_20 autocorrelation matrix of formula_21. The autocorrelation matrix formula_22 is traditionally estimated using sample correlation matrix  where formula_24 is the number of vector observations and formula_25. Given the estimate of formula_22, MUSIC estimates the frequency content of the signal or autocorrelation matrix using an eigenspace method. Since formula_22 is a Hermitian matrix, all of its formula_11 eigenvectors formula_29 are orthogonal to each other. If the eigenvalues of formula_22 are sorted in decreasing order, the eigenvectors formula_31 corresponding to the formula_2 largest eigenvalues (i.e. directions of largest variability) span the signal subspace formula_33. The remaining formula_34 eigenvectors correspond to eigenvalue equal to formula_16 and span the noise subspace formula_36, which is orthogonal to the signal subspace, formula_37 . Note that for formula_38, 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 formula_39 that resides in the signal subspace formula_40 must be orthogonal to the noise subspace, formula_41, it must be that formula_42 for all the eigenvectors formula_43 that spans the noise subspace. In order to measure the degree of orthogonality of formula_39 with respect to all the formula_45, the MUSIC algorithm defines a squared norm where the matrix formula_47 is the  matrix of eigenvectors that span the noise subspace formula_36. If formula_40, then formula_50 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 formula_52 are the noise eigenvectors and is the candidate steering vector. The locations of the formula_2 largest peaks of the estimation function give the frequency estimates for the formula_2 signal components MUSIC is a generalization of Pisarenko's method, and it reduces to Pisarenko's method when formula_57. 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. Comparison to other methods. 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. In addition , MUSIC assumes coexistent sources to be uncorrelated, which limits its practical applications. Recent iterative semi-parametric methods offer robust superresolution despite of highly correlated sources, e.g., SAMV Other applications. A modified version of MUSIC, denoted as Time-Reversal MUSIC (TR-MUSIC) has been recently applied to computational time-reversal imaging. 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.