  The paper explores the problem of \emph{spectral compressed sensing}, which
aims to recover a spectrally sparse signal from a small random subset of its
$n$ time domain samples. The signal of interest is assumed to be a
superposition of $r$ multi-dimensional complex sinusoids, while the underlying
frequencies can assume any \emph{continuous} values in the normalized frequency
domain. Conventional compressed sensing paradigms suffer from the basis
mismatch issue when imposing a discrete dictionary on the Fourier
representation. To address this issue, we develop a novel algorithm, called
\emph{Enhanced Matrix Completion (EMaC)}, based on structured matrix completion
that does not require prior knowledge of the model order. The algorithm starts
by arranging the data into a low-rank enhanced form exhibiting multi-fold
Hankel structure, and 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 $r\log^{4}n$, and is stable against
bounded noise. Even if a constant portion of samples are corrupted with
arbitrary magnitude, EMaC still allows exact recovery, provided that the sample
complexity exceeds the order of $r^{2}\log^{3}n$. Along the way, our results
demonstrate the power of convex relaxation in completing a low-rank multi-fold
Hankel or Toeplitz matrix from minimal observed entries. The performance of our
algorithm and its applicability to super resolution are further validated by
numerical experiments.
