  This paper considers reconstructing a spectrally sparse signal from a small
number of randomly observed time-domain samples. The signal of interest is a
linear combination of complex sinusoids at $R$ distinct frequencies. The
frequencies can assume any continuous values in the normalized frequency domain
$[0,1)$. After converting the spectrally sparse signal recovery into a low rank
structured matrix completion problem, we propose an efficient feasible point
approach, named projected Wirtinger gradient descent (PWGD) algorithm, to
efficiently solve this structured matrix completion problem. We further
accelerate our proposed algorithm by a scheme inspired by FISTA. We give the
convergence analysis of our proposed algorithms. Extensive numerical
experiments are provided to illustrate the efficiency of our proposed
algorithm. Different from earlier approaches, our algorithm can solve problems
of very large dimensions very efficiently.
