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_30: We obtain the best approximation in L 1(ℝ), by entire functions of exponential type, for a class of even functions that includes e −λ|x|, where λ>0, log |x| and |x| α , where −1<α<1. We also give periodic versions of these results where the approximating functions are trigonometric polynomials of bounded degree.
@cite_37: Super-resolution is a fundamental task in imaging, where the goal is to extract fine-grained structure from coarse-grained measurements. Here we are interested in a popular mathematical abstraction of this problem that has been widely studied in the statistics, signal processing and machine learning communities. We exactly resolve the threshold at which noisy super-resolution is possible. In particular, we establish a sharp phase transition for the relationship between the cutoff frequency (m) and the separation (Δ). If m > 1 Δ + 1, our estimator converges to the true values at an inverse polynomial rate in terms of the magnitude of the noise. And when m
@cite_22: We prove sharp lower bounds for the smallest singular value of a partial Fourier matrix with arbitrary "off the grid" nodes (equivalently, a rectangular Vandermonde matrix with the nodes on the unit circle), in the case when some of the nodes are separated by less than the inverse bandwidth. The bound is polynomial in the reciprocal of the so-called "super-resolution factor", while the exponent is controlled by the maximal number of nodes which are clustered together. As a corollary, we obtain sharp minimax bounds for the problem of sparse super-resolution on a grid under the partial clustering assumptions.
@cite_1: We prove upper and lower bounds for the spectral condition number of rectangular Vandermonde matrices with nodes on the complex unit circle. The nodes are "off the grid", pairs of nodes nearly collide, and the studied condition number grows linearly with the inverse separation distance. We provide reasonable sharp constants that are independent from the number of nodes as long as non-colliding nodes are well-separated.
@cite_13: Super-resolution refers to the process of recovering the locations and amplitudes of a collection of point sources, represented as a discrete measure, given @math of its noisy low-frequency Fourier coefficients. The recovery process is highly sensitive to noise whenever the distance @math between the two closest point sources is less than @math . This paper studies the fundamental difficulty of super-resolution and the performance guarantees of a subspace method called MUSIC in the regime that @math . The most important quantity in our theory is the minimum singular value of the Vandermonde matrix whose nodes are specified by the source locations. Under the assumption that the nodes are closely spaced within several well-separated clumps, we derive a sharp and non-asymptotic lower bound for this quantity. Our estimate is given as a weighted @math sum, where each term only depends on the configuration of each individual clump. This implies that, as the noise increases, the super-resolution capability of MUSIC degrades according to a power law where the exponent depends on the cardinality of the largest clump. Numerical experiments validate our theoretical bounds for the minimum singular value and the resolution limit of MUSIC. When there are @math point sources located on a grid with spacing @math , the fundamental difficulty of super-resolution can be quantitatively characterized by a min-max error, which is the reconstruction error incurred by the best possible algorithm in the worst-case scenario. We show that the min-max error is closely related to the minimum singular value of Vandermonde matrices, and we provide a non-asymptotic and sharp estimate for the min-max error, where the dominant term is @math .
The minimum singular value of a Vandermonde matrix highly depends on the configuration of its nodes. The best available bound for the case @math was provided in @cite_37 , which relied on the Beurling-Selberg machinery, see @cite_30 . Recently there are several independent works which provide estimates for @math by incorporating additional geometric information about the support set, see @cite_22 @cite_13 @cite_1 . Accurate lower bounds under a clumps model can be found in @cite_13 .