  This paper explores robust recovery of a superposition of $R$ distinct
complex exponential functions from a few random Gaussian projections. We assume
that the signal of interest is of $2N-1$ dimensional and $R<<2N-1$. This
framework covers a large class of signals arising from real applications in
biology, automation, imaging science, etc. To reconstruct such a signal, our
algorithm is to seek a low-rank Hankel matrix of the signal by minimizing its
nuclear norm subject to the consistency on the sampled data. Our theoretical
results show that a robust recovery is possible as long as the number of
projections exceeds $O(R\ln^2N)$. No incoherence or separation condition is
required in our proof. Our method can be applied to spectral compressed sensing
where the signal of interest is a superposition of $R$ complex sinusoids.
Compared to existing results, our result here does not need any separation
condition on the frequencies, while achieving better or comparable bounds on
the number of measurements. Furthermore, our method provides theoretical
guidance on how many samples are required in the state-of-the-art non-uniform
sampling in NMR spectroscopy. The performance of our algorithm is further
demonstrated by numerical experiments.
