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.
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 .
@cite_30 @cite_37 @cite_22 @cite_1 @cite_13
2963373272 1554357707 2962832549 2892315708
Abstract We derive bounds on the extremal singular values and the condition number of N × K , with N ⩾ K , Vandermonde matrices with nodes in the unit disk. The mathematical techniques we develop to prove our main results are inspired by a link—first established by Selberg [1] and later extended by Moitra [2] —between the extremal singular values of Vandermonde matrices with nodes on the unit circle and large sieve inequalities. Our main conceptual contribution lies in establishing a connection between the extremal singular values of Vandermonde matrices with nodes in the unit disk and a novel large sieve inequality involving polynomials in z ∈ C with | z | ⩽ 1 . Compared to Bazan's upper bound on the condition number [3] , which, to the best of our knowledge, constitutes the only analytical result—available in the literature—on the condition number of Vandermonde matrices with nodes in the unit disk, our bound not only takes a much simpler form, but is also sharper for certain node configurations. Moreover, the bound we obtain can be evaluated consistently in a numerically stable fashion, whereas the evaluation of Bazan's bound requires the solution of a linear system of equations which has the same condition number as the Vandermonde matrix under consideration and can therefore lead to numerical instability in practice. As a byproduct, our result—when particularized to the case of nodes on the unit circle—slightly improves upon the Selberg–Moitra bound. The purpose of this paper is to study the conditioning of complex Vandermonde matrices, in reference to applications such as superresolution and the problem of recovering missing samples in band-limited signals. The results include bounds for the singular values of Vandermonde matrices whose nodes are complex numbers on the unit circle. It is shown that, under certain conditions, such matrices can be quite well-conditioned, contrarily to what happens in the real case. Estimation of the condition numbers of Vandermonde matrices, motivated by applications to interpolation and quadrature, can be traced back to at least the 1970s. Empirical study has consistently shown that Vandermonde matrices tend to be badly ill-conditioned, with a narrow class of exceptions, such as the matrices of the discrete Fourier transform (hereafter we use the acronym DFT). So far, however, formal support for this empirical observation has been limited to the matrices defined by the real set of knots. We prove that, more generally, any Vandermonde matrix of a large size is badly ill-conditioned unless its knots are more or less equally spaced on or about the circle @math . The matrices of the DFT are unitary up to scaling and therefore perfectly conditioned. They are defined by a cyclic sequence of knots, equally spaced on that circle, but we prove that even a slight modification of the knots into the so-called quasi-cyclic sequence on this circle defines badly ill-conditioned Vandermond... 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. This generalizes previously known results for the extreme cases when all of the nodes either form a single cluster, or are completely separated. We briefly discuss possible implications for the theory and practice of super-resolution under sparsity constraints.