The Threshold for Super-resolution via Extremal Functions.
Ankur Moitra · arXiv (Cornell University) · 2014
Super-resolution is a natural mathematical abstraction for the problem of extracting fine-grained structure from coarse-grained measurements, and has received considerable attention following the pio-neering works of Donoho [11] and Candes and Fernandez-Granda [5, 6]. Here we introduce new techniques based on extremal functions for studying this and related problems and 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 < (1−)/ ∆ no estimator can distinguish between a particular pair of ∆-separated signals even if the magnitude of the noise is exponentially small. Our results involve making novel connections between extremal functions and spectral properties of the Vandermonde matrix, such as bounding its condition number as well as constructing explicit preconditioners for it.