Compressive sensing off the grid

We consider the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressive sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0, 1]. We propose an atomic norm minimization approach to exactly recover the unobserved samples, which is then followed by any linear prediction method to identify the frequency components. We reformulate the atomic norm minimization as an exact semidefinite program. By constructing a dual certificate polynomial using random kernels, we show that roughly s log s log n random samples are sufficient to guarantee the exact frequency estimation with high probability, provided the frequencies are well separated. Extensive numerical experiments are performed to illustrate the effectiveness of the proposed method. Our approach avoids the basis mismatch issue arising from discretization by working directly on the continuous parameter space. Potential impact on both compressive sensing and line spectral estimation, in particular implications in sub-Nyquist sampling and super-resolution, are discussed.