The recoverability limit for superresolution via sparsity

We consider the problem of robustly recovering a $k$-sparse coefficient vector from the Fourier series that it generates, restricted to the interval $[- Ω, Ω]$. The difficulty of this problem is linked to the superresolution factor SRF, equal to the ratio of the Rayleigh length (inverse of $Ω$) by the spacing of the grid supporting the sparse vector. In the presence of additive deterministic noise of norm $σ$, we show upper and lower bounds on the minimax error rate that both scale like $(SRF)^{2k-1} σ$, 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 $σ$-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.