A nonconvex optimization approach to spectral estimation 

The spectral estimation problem is to approximate the unknown frequencies and amplitudes of a Fourier sum from noisy time samples. The celebrated MUSIC algorithm approximates the signal frequencies by creating a special function and finding its smallest local minima through a grid search. We introduce the Gradient-MUSIC algorithm, which instead finds local minima through local optimization with carefully chosen initialization, making it significantly more efficient and eliminates the need for discretization over a fine grid. Even though the optimization landscape is nonconvex, Gradient-MUSIC provably finds suitable initialization and gradient descent converges at a linear rate. Under natural assumptions, Gradient-MUSIC estimates the signal parameters at their minimax optimal rates for several deterministic and random noise models. Unlike many other spectral estimation algorithms, the mechanisms of Gradient-MUSIC are highly flexible, and has a canonical extendion to the multidimensional setting with nonuniform sampling geometries. Joint work with Albert Fannjiang and Wenjing Liao.