Atomic norm denoising with applications to line spectral estimation

The sub-Nyquist estimation of line spectra is a classical problem in signal processing, but currently popular subspace-based techniques have few guarantees in the presence of noise and rely on a priori knowledge about system model order. Motivated by recent work on atomic norms in inverse problems, we propose a new approach to line spectrum estimation that provides theoretical guarantees for the mean-square-error performance in the presence of noise and without advance knowledge of the model order. We propose an abstract theory of denoising with atomic norms which is specialized to provide a convex optimization problem for estimating the frequencies and phases of a mixture of complex exponentials with guaranteed bounds on the mean-squared-error. In general, our proposed optimization problem has no known polynomial time solution, but we provide an efficient algorithm, called DAST, based on the Fast Fourier Transform that achieves nearly the same error rate. We compare DAST with Cadzow's canonical alternating projection algorithm, which performs marginally better under high signal-to-noise ratios when the model order is known exactly, and demonstrate experimentally that DAST outperforms other denoising techniques, including Cadzow's, over a wide range of signal-to-noise ratios.