SUPERRESOLUTION VIA SPARSITY CONSTRAINTS

Consider the problem of recovering a measure-mu supported on a lattice of span DELTA, when measurements are only available concerning the Fourier Transform mu(omega) at frequencies \omega\ less-than-or-equal-to OMEGA. If OMEGA is much smaller than the Nyquist frequency pi/DELTA and the measurements are noisy, then, in general, stable recovery of mu is impossible. In this paper it is shown that if, in addition, we know that the measure-mu 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 4-pi/OMEGA . R there are at most R elements. Indeed, if the (unknown) support of mu 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 DELTA-2R-1 as DELTA --> 0. This result validates certain practical efforts, in spectroscopy, seismic prospecting, and astronomy, to provide superresolution by imposing support limitations in reconstruction. The results amount to inequalities for interpolation of entire functions of exponential type from values at special point sets which are irregular, yet internally balanced, uniformly discrete, and of uniform density 1.