  This paper establishes a nearly optimal algorithm for estimating the
frequencies and amplitudes of a mixture of sinusoids from noisy equispaced
samples. We derive our algorithm by viewing line spectral estimation as a
sparse recovery problem with a continuous, infinite dictionary. We show how to
compute the estimator via semidefinite programming and provide guarantees on
its mean-square error rate. We derive a complementary minimax lower bound on
this estimation rate, demonstrating that our approach nearly achieves the best
possible estimation error. Furthermore, we establish bounds on how well our
estimator localizes the frequencies in the signal, showing that the
localization error tends to zero as the number of samples grows. We verify our
theoretical results in an array of numerical experiments, demonstrating that
the semidefinite programming approach outperforms two classical spectral
estimation techniques.
