Compressed Sensing Off the Grid

TLDR

Compressed sensing typically assumes grid‑aligned frequencies, but here frequencies may take any value in the interval [0, 1]. The study aims to estimate the frequencies of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. An atomic‑norm minimization method, reformulated as a semidefinite program, is used to recover missing samples and identify frequencies, and numerical experiments demonstrate its effectiveness. The method requires only O(s log s log n) random samples to achieve exact frequency localization with high probability when frequencies are well separated.

Abstract

This paper investigates 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 compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0, 1]. An atomic norm minimization approach is proposed to exactly recover the unobserved samples and identify the unknown frequencies, which is then reformulated as an exact semidefinite program. Even with this continuous dictionary, it is shown that O(slog s log n) random samples are sufficient to guarantee exact frequency localization with high probability, provided the frequencies are well separated. Extensive numerical experiments are performed to illustrate the effectiveness of the proposed method.