The problem of imaging point objects can be formulated as estimation of an unknown atomic measure from its @math consecutive noisy Fourier coefficients. The standard resolution of this inverse problem is @math and super-resolution refers to the capability of resolving atoms at a higher resolution. When any two atoms are less than @math apart, this recovery problem is highly challenging and many existing algorithms either cannot deal with this situation or require restrictive assumptions on the sign of the measure. ESPRIT (Estimation of Signal Parameters via Rotation Invariance Techniques) is an efficient method that does not depend on the sign of the measure and this paper provides a : we prove an explicit upper bound on the recovery error of ESPRIT in terms of the minimum singular value of Vandermonde matrices. Using prior estimates for the minimum singular value explains its resolution limit -- when the support of @math consists of multiple well-separated clumps, the noise level that ESPRIT can tolerate scales like @math , where the super-resolution factor @math governs the difficulty of the problem and @math is the cardinality of the largest clump. Our theory is validated by numerical experiments.
@cite_10: 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.
@cite_3: 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...
Prior works @cite_3 @cite_10 addressed super-resolution from an information theoretic view. They considered the situation where the atoms are located on a grid on @math with spacing @math and the given information consists of noisy continuous Fourier measurements. Both papers derived lower and upper bounds for a min-max error. These results showed that @math minimization is optimal for this discrete model, but it is not computationally feasible. ESPRIT is a polynomial-time algorithm that can be used for the more general off-the-grid-model". The investigation of the optimality of ESPRIT is an interesting future research direction.