  Let $x\in\mathbb{C}^n$ be a spectrally sparse signal consisting of $r$
complex sinusoids with or without damping. We consider the spectral compressed
sensing problem, which is about reconstructing $x$ from its partial revealed
entries. By utilizing the low rank structure of the Hankel matrix corresponding
to $x$, we develop a computationally efficient algorithm for this problem. The
algorithm starts from an initial guess computed via one-step hard thresholding
followed by projection, and then proceeds by applying projected gradient
descent iterations to a non-convex functional. Based on the sampling with
replacement model, we prove that $O(r^2\log(n))$ observed entries are
sufficient for our algorithm to achieve the successful recovery of a spectrally
sparse signal. Moreover, extensive empirical performance comparisons show that
our algorithm is competitive with other state-of-the-art spectral compressed
sensing algorithms in terms of phase transitions and overall computational
time.
