Compressive Two-Dimensional Harmonic Retrieval via Atomic Norm Minimization

This paper is concerned with estimation of two-dimensional (2-D) frequencies from partial time samples, which arises in many applications such as radar, inverse scattering, and super-resolution imaging. Suppose that the object under study is a mixture of r continuous-valued 2-D sinusoids. The goal is to identify all frequency components when we only have information about a random subset of n regularly spaced time samples. We demonstrate that under some mild spectral separation condition, it is possible to exactly recover all frequencies by solving an atomic norm minimization program, as long as the sample complexity exceeds the order of rlogrlogn. We then propose to solve the atomic norm minimization via a semidefinite program and provide numerical examples to justify its practical ability. Our work extends the framework proposed by Tang for line spectrum estimation to 2-D frequency models.