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 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/ ) (up to log factors). Previous algorithms require a cutoff frequency which may be as large as ⌦(
• 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 . 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 hypergrid). Furthermore, our analysis and algorithm are elementary (based on concentration bounds for sampling and the singular value decomposition).
The paper analyzes the problem of super-resolving a collection of spikes from low-pass measurements. It introduces an algebraic approach based on tensor factorization. For k spikes, suggests taking about k log k random locations in Fourier space, plus d deterministic locations, and then sampling on a grid of size (k log k + d)^3 corresponding to all ways of summing three of these locations. Because of the algebraic properties of Fourier measurements, the resulting 3-tensor is of rank k (up to noise). The paper proves that with high probability in the sample locations, the matrix of factors is well-conditioned, and hence the factors can be stably recovered using linear algebraic manipulations. These results are stable under small deterministic noise. An attractive aspect of the approach is that the requirements do not depend exponentially on the signal dimension. There are two main downsides. The first is that the approach is suboptimal from the perspective of compressed sensing - it intrinsically requires k^3 measurements to recover k spikes. The second is that the stability result is limited to very small noise. This may be an artifact of the analysis, or may be intrinsic to this approach. It is somewhat difficult to judge, because numerical results are not provided. Comments in the response would be appreciated. The main (clever) idea here is the reduction of the problem to 3-tensor decomposition; after this, the analysis follows in a natural way. The submission does not provide much basis for evaluating the practicality of the approach. However, from a theoretical perspective it obtains scalings (esp. in higher dimensions, where the number of samples required does not depend exponentially on d) that to my knowledge were not available using previous approaches.  Minor commentsIn the comparison with the work of Candes and Fernandez-Granda [3], it should be mentioned that [3] allows general complex-valued amplitudes. The setup of this submission restricts the amplitudes to lie between zero and one. There are results of Candes and Morgenshtern on the arxiv for this setup, which might be a more relevant point of comparison. The analysis of noisy tensor decomposition forces the noise level to be very small -of \ell^\infty norm about 1/k^4. An advantage is that the noise can be arbitrary. Can the authors comment: (a) is this restriction an artifact of the tensor decomposition algorithm adopted here and its analysis, or an intrinsic limitation to the proposed approach, and (b) can a better stability result be obtained with stochastic (say, Gaussian) noise? The submission appears to have been written in a hurry. Please spellcheck. Also, "One useful fact..." [line 060] is false. I understand what is intended, but that kind of a typo that early on doesn't build confidence. It most applications that this reviewer is aware of, d is a small constant, and so measuring \Delta in L^2 vs L^\infty does not make a substantial difference.