Super-Resolution Off the Grid
  Super-resolution is the problem of recovering a superposition of point
sources using bandlimited measurements, which may be corrupted with noise. This
signal processing problem arises in numerous imaging problems, ranging from
astronomy to biology to spectroscopy, where it is common to take (coarse)
Fourier measurements of an object. Of particular interest is in obtaining
estimation procedures which are robust to noise, with the following desirable
statistical and computational properties: we seek to use coarse Fourier
measurements (bounded by some cutoff frequency); we hope to take a
(quantifiably) small number of measurements; we desire our algorithm to run
quickly.
  Suppose we have k point sources in d dimensions, where the points are
separated by at least \Delta from each other (in Euclidean distance). This work
provides an algorithm with the following favorable guarantees: - The algorithm
uses Fourier measurements, whose frequencies are bounded by O(1/\Delta) (up to
log factors). Previous algorithms require a cutoff frequency which may be as
large as {\Omega}( d/\Delta). - The number of measurements taken by and the
computational complexity of our algorithm are bounded by a polynomial in both
the number of points k and the dimension d, with no dependence on the
separation \Delta. In contrast, previous algorithms depended inverse
polynomially on the minimal separation and exponentially on the dimension for
both of these quantities.
  Our estimation procedure itself is simple: we take random bandlimited
measurements (as opposed to taking an exponential number of measurements on the
hyper-grid). Furthermore, our analysis and algorithm are elementary (based on
concentration bounds for sampling and the singular value decomposition).
