Near Minimax Line Spectral Estimation

Abstract

This paper establishes a nearly optimal algorithm for estimating the frequencies and amplitudes of a mixture of sinusoids from noisy equispaced samples. We derive our algorithm by viewing line spectral estimation as a sparse recovery problem with a continuous, infinite dictionary. We show how to compute the estimator via semidefinite programming and provide guarantees on its mean-square error rate. We derive a complementary minimax lower bound on this estimation rate, demonstrating that our approach nearly achieves the best possible estimation error. Furthermore, we establish bounds on how well our estimator localizes the frequencies in the signal, showing that the localization error tends to zero as the number of samples grows. We verify our theoretical results in an array of numerical experiments, demonstrating that the semidefinite programming approach outperforms two classical spectral estimation techniques.

25 pages, 12 figures. Added a numerical experiments section

References in corpus (6)

• Simultaneous analysis of Lasso and Dantzig selector
• Support detection in super-resolution
• Compressed Sensing off the Grid
• Atomic norm denoising with applications to line spectral estimation
• Super-Resolution from Noisy Data
• Spike detection from inaccurate samplings

Cited by in corpus (9)

• The recoverability limit for superresolution via sparsity
• Compressive parameter estimation in AWGN
• Super-resolution on the Sphere using Convex Optimization
• Exact Joint Sparse Frequency Recovery via Optimization Methods
• Exact Support Recovery for Sparse Spikes Deconvolution
• Sharp recovery bounds for convex demixing, with applications
• Spike detection from inaccurate samplings
• Compressed Subspace Matching on the Continuum
• Efficient First-Order Algorithms for Adaptive Signal Denoising