The recoverability limit for superresolution via sparsity

Abstract

We consider the problem of robustly recovering a $k$-sparse coefficient vector from the Fourier series that it generates, restricted to the interval $[-\Omega ,\Omega ]$. The difficulty of this problem is linked to the superresolution factor SRF, equal to the ratio of the Rayleigh length (inverse of $\Omega$) by the spacing of the grid supporting the sparse vector. In the presence of additive deterministic noise of norm $\sigma$, we show upper and lower bounds on the minimax error rate that both scale like $(SRF{)}^{2k-1}\sigma$, providing a partial answer to a question posed by Donoho in 1992. The scaling arises from comparing the noise level to a restricted isometry constant at sparsity $2k$, or equivalently from comparing $2k$ to the so-called $\sigma$-spark of the Fourier system. The proof involves new bounds on the singular values of restricted Fourier matrices, obtained in part from old techniques in complex analysis.

19 pages

References in corpus (1)

• Near Minimax Line Spectral Estimation

Cited by in corpus (15)

• MUSIC for multidimensional spectral estimation: stability and super-resolution
• Deep learning for low frequency extrapolation of multicomponent data in elastic full waveform inversion
• Stable super-resolution limit and smallest singular value of restricted Fourier matrices
• Mathematical Theory of Computational Resolution Limit in Multi-dimensions
• Support Recovery for Sparse Deconvolution of Positive Measures
• Accuracy of spike-train Fourier reconstruction for colliding nodes
• Super-resolution limit of the ESPRIT algorithm
• A Theory of Computational Resolution Limit for Line Spectral Estimation
• On the Stable Resolution Limit of Total Variation Regularization for Spike Deconvolution
• A mathematical theory of computational resolution limit in one dimension
• Conditioning of restricted Fourier matrices and super-resolution of MUSIC
• Single-exponential bounds for the smallest singular value of Vandermonde matrices in the sub-Rayleigh regime
• Prony Scenarios and Error Amplification in a Noisy Spike-Train Reconstruction
• Algebraic Geometry of Error Amplification: the Prony leaves
• On algebraic properties of low rank approximations of Prony systems