  Line spectral estimation theory aims to estimate the off-the-grid spectral
components of a time signal with optimal precision. Recent results have shown
that it is possible to recover signals having sparse line spectra from few
temporal observations via the use of convex programming. However, the
computational cost of such approaches remains the major flaw to their
application to practical systems. This work investigates the recovery of
spectrally sparse signal from low-dimensional partial measurements. It is shown
in the first part of this paper that, under a light assumption on the
sub-sampling matrix, the partial line spectral estimation problems can be
relaxed into a low-dimensional semidefinite program. The proof technique relies
on a novel extension of the Gram parametrization to subspaces of trigonometric
polynomials.
  The second part of this work focuses on the analysis of two particular
sub-sampling patterns: multirate sampling and random selection sampling. It is
shown that those sampling patterns guarantee perfect recovery of the line
spectra, and that the reconstruction can be achieved in a poly-logarithmic time
with respect to the full observation case. Moreover, the sub-Nyquist recovery
capabilities of such sampling patterns are highlighted. The atomic soft
thresholding method is adapted in the presented framework to estimate sparse
spectra in noisy environments, and a scalable algorithm for its resolution is
proposed.
