Super-Resolution Limit of the ESPRIT Algorithm

DOI10.1109/TIT.2020.2974174MaRDI QIDQ5124450zbMATH OpenOpenAlexFDO

Authors Weilin Li, Wenjing Liao, Albert Fannjiang

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.03782

Mathematics Subject Classification ID

Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: The problem of imaging point objects can be formulated as estimation of an unknown atomic measure from its $M+1$ consecutive noisy Fourier coefficients. The standard resolution of this inverse problem is $1/M$ and super-resolution refers to the capability of resolving atoms at a higher resolution. When any two atoms are less than $1/M$ 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 is an efficient method that does not depend on the sign of the measure. This paper provides an explicit error bound on the support matching distance of ESPRIT in terms of the minimum singular value of Vandermonde matrices. When the support consists of multiple well-separated clumps and noise is sufficiently small, the support error by ESPRIT scales like ${mSRF}^{2lambda+2}imesmNoise$, where the Super-Resolution Factor ($mSRF$) governs the difficulty of the problem and $lambda$ is the cardinality of the largest clump. {If the support contains one clump of closely spaced atoms, the min-max error is ${mSRF}^{2lambda+2}imesmNoise/M$. Our error bound matches the min-max rate up to a factor of $M$ in the small noise regime. Our results therefore establishes the near-optimality of ESPRIT,} and our theory is validated by numerical experiments.

Cited in

(32)

• Single-exponential bounds for the smallest singular value of Vandermonde matrices in the sub-Rayleigh regime
• Cautious active clustering
• Super-resolution of positive sources on an arbitrarily fine grid
• Quantization for spectral super-resolution
• Multivariate Vandermonde matrices with separated nodes on the unit circle are stable
• Super-resolution wavelets for recovery of arbitrarily close point-masses with arbitrarily small coefficients
• On the smallest singular value of multivariate Vandermonde matrices with clustered nodes
• The spectral properties of Vandermonde matrices with clustered nodes
• Stable super-resolution limit and smallest singular value of restricted Fourier matrices
• Approximate super-resolution of positive measures in all dimensions
• Superresolution via Sparsity Constraints
• Super strong ETH is true for PPSZ with small resolution width
• Geometry of error amplification in solving the Prony system with near-colliding nodes
• Conditioning of partial nonuniform Fourier matrices with clustered nodes
• Super-resolution of generalized spikes and spectra of confluent Vandermonde matrices
• A note on spike localization for line spectrum estimation
• IFF: A Superresolution Algorithm for Multiple Measurements
• Short Communication: Weak Sparse Superresolution is Well-Conditioned
• Separation-free spectral super-resolution via convex optimization
• Improved resolution estimate for the two-dimensional super-resolution and a new algorithm for direction of arrival estimation with uniform rectangular array
• Approximation and interpolation of singular measures by trigonometric polynomials
• A sparse array direction-finding approach under impulse noise
• A perturbative analysis for noisy spectral estimation
• Mathematical foundation of sparsity-based multi-snapshot spectral estimation
• On the accuracy of Prony's method for recovery of exponential sums with closely spaced exponents
• Nonharmonic multivariate Fourier transforms and matrices: condition numbers and hyperplane geometry
• Multiscale estimates for the condition number of non-harmonic Fourier matrices
• Optimal Extrapolation Bounds for Sparse Fourier Sums
• A signal separation view of classification
• Optimality of gradient-MUSIC for spectral estimation
• Adaptive local representations for Helmholtz Trefftz discontinuous Galerkin methods
• Towards a theory of stable super-resolution: model-based formulation and stability analysis

This page was built for publication: Super-Resolution Limit of the ESPRIT Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124450)