  The line spectral estimation problem consists in recovering the frequencies
of a complex valued time signal that is assumed to be sparse in the spectral
domain from its discrete observations. Unlike the gridding required by the
classical compressed sensing framework, line spectral estimation reconstructs
signals whose spectral supports lie continuously in the Fourier domain. If
recent advances have shown that atomic norm relaxation produces highly robust
estimates in this context, the computational cost of this approach remains,
however, the major flaw for its application to practical systems.
  In this work, we aim to bridge the complexity issue by studying the atomic
norm minimization problem from low dimensional projection of the signal
samples. We derive conditions on the sub-sampling matrix under which the
partial atomic norm can be expressed by a low-dimensional semidefinite program.
Moreover, we illustrate the tightness of this relaxation by showing that it is
possible to recover the original signal in poly-logarithmic time for two
specific sub-sampling patterns.
