We consider the problem of robustly recovering a @math -sparse coefficient vector from the Fourier series that it generates, restricted to the interval @math . The difficulty of this problem is linked to the superresolution factor SRF, equal to the ratio of the Rayleigh length (inverse of @math ) by the spacing of the grid supporting the sparse vector. In the presence of additive deterministic noise of norm @math , we show upper and lower bounds on the minimax error rate that both scale like @math , 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 @math , or equivalently from comparing @math to the so-called @math -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.
Corollary addresses a special case of a question originally raised by Donoho in 1992 in @cite_16 . In that paper, Donoho recognizes that the sparse clumps" signal model is the right notion to achieve superresolution. Given a vector @math , he lets @math for the smallest integer such that the number of nonzero elements of @math is at most @math within any consecutive subset of cardinality @math times the Rayleigh length. Clearly, the set of vectors that satisfies Donoho's model at level @math includes the @math -sparse vectors. If @math denotes the minimax error of estimating a vector at level @math , under deterministic noise of level @math in @math , then Donoho showed that [ C_ 1,r (SRF)^ 2r-1 E(r, ) C_ 2,r (SRF)^ 2r+1 . ] Corollary is the statement that there is no gap in this sequence of inequalities --- and that Donoho's lower bound gives the correct scaling --- albeit when @math is understood as sparsity rather than the more general (and more relevant) sparse clumps" model. It would be very interesting to close the exponent gap in the latter case as well.
@cite_16
2018778093
Consider the problem of recovering a measure @math supported on a lattice of span @math , when measurements are only available concerning the Fourier Transform @math at frequencies @math . If @math is much smaller than the Nyquist frequency @math and the measurements are noisy, then, in general, stable recovery of @math is impossible. In this paper it is shown that if, in addition, we know that the measure @math satisfies certain sparsity constraints, then stable recovery is possible. Say that a set has Rayleigh index less than or equal to R if in any interval of length @math there are at most R elements. Indeed, if the (unknown) support of @math is known, a priori, to have Rayleigh index at most R, then stable recovery is possible with a stability coefficient that grows at most like @math as @math . This result validates certain practical efforts, in spectroscopy, seismic prospecting, and astrono...