FAST MUSIC – An Efficient Implementation Of The Music Algorithm For Frequency Estimation Of Approximately Periodic Signals
Noise subspace methods are popular for estimating the parameters of complex sinusoids in the presence of uncorrelated noise and have applications in musical instrument modeling and microphone array processing. One such algorithm, MUSIC (Multiple Signal Classification) has been popular for its ability to resolve closely spaced sinusoids. However, the computational efficiency of MUSIC is relatively low, since it requires an explicit eigenvalue decomposition of an autocorrelation matrix, followed by a linear search over a large space. In this paper, we discuss methods for and the benefits of converting the Toeplitz structure of the autocorrelation matrix to circulant form, so that eigenvalue decomposition can be replaced by a Fast Fourier Transform (FFT) of one row of the matrix. This transformation requires modeling the signal as at least approximately periodic over some duration. For these periodic signals, the pseudospectrum calculation becomes trivial and the accuracy of the frequency estimates only depends on how well periodicity detection works. We derive a closed-form expression for the pseudospectrum, yielding large savings in computation time. We test our algorithm to resolve closely spaced piano partials.