Optimality of Gradient-MUSIC for spectral estimation

We introduce the Gradient-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 1D landscape to find initialization simultaneously for all frequencies followed by parallelizable local refinement via gradient descent. We also analyze 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 1D 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 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 error at most $C\varepsilon/m$ and $C\varepsilon$ respectively, which are minimax optimal in $m$ and $\varepsilon$. 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.