Optimality of gradient-MUSIC for spectral estimation

Abstract We introduce the Gradient-MUltiple SIgnal Classification (MUSIC) algorithm for estimating the unknown frequencies and amplitudes of a nonharmonic signal from noisy time samples. While the classical MUSIC algorithm performs a computationally expensive search over a fine grid, Gradient-MUSIC is significantly more efficient and eliminates the need for discretization over a fine grid by using optimization techniques. It coarsely scans the one-dimensional landscape to find initialization simultaneously for all frequencies followed by parallelizable local refinement via gradient descent. We also analyse its performance when the noise level is sufficiently small and the signal frequencies are separated by at least $8\pi /m$, where $\pi /m$ is the standard resolution of this problem. Even though the one-dimensional landscape is nonconvex, we prove a global convergence result for Gradient-MUSIC: coarse scanning provably finds suitable initialization and gradient descent converges at a linear rate. In addition to the convergence results, we also upper bound the error between the true signal frequencies and amplitudes with those found by Gradient-MUSIC. For example, if the noise has $\ell ^\infty$ norm at most $\varepsilon$, then the frequencies and amplitudes are recovered up to an error of at most $C\varepsilon /m$ and $C\varepsilon$ respectively for a universal $C>0$, which are minimax optimal in $m$, $\varepsilon$, and the number of frequencies. Our theory can also handle stochastic noise with performance guarantees under nonstationary independent Gaussian noise. Our main approach is a comprehensive geometric analysis of the landscape, a perspective that has not been explored before.