  The paper studies the problem of recovering a spectrally sparse object from a
small number of time domain samples. Specifically, the object of interest with
ambient dimension $n$ is assumed to be a mixture of $r$ complex
multi-dimensional sinusoids, while the underlying frequencies can assume any
value in the unit disk. Conventional compressed sensing paradigms suffer from
the {\em basis mismatch} issue when imposing a discrete dictionary on the
Fourier representation. To address this problem, we develop a novel
nonparametric algorithm, called enhanced matrix completion (EMaC), based on
structured matrix completion. The algorithm starts by arranging the data into a
low-rank enhanced form with multi-fold Hankel structure, then attempts recovery
via nuclear norm minimization. Under mild incoherence conditions, EMaC allows
perfect recovery as soon as the number of samples exceeds the order of
$\mathcal{O}(r\log^{2} n)$. We also show that, in many instances, accurate
completion of a low-rank multi-fold Hankel matrix is possible when the number
of observed entries is proportional to the information theoretical limits
(except for a logarithmic gap). The robustness of EMaC against bounded noise
and its applicability to super resolution are further demonstrated by numerical
experiments.
