Inferring the fine scale properties of a signal from its coarse measurements is a common signal processing problem that finds a myriad of applications in various areas of experimental sciences. Line spectral estimation is probably one of the most iconic instances of this category of problems and consists of recovering the locations of highly localized patterns, or spikes, in the spectrum of a time signal by observing a finite number of its uniform samples. Recent advances have shown that convex programming could be used to estimate the frequency components of a spectrally sparse signal. This thesis focuses on the total variation (TV) approach to perform this reconstruction.

It is conjectured that a phase transition on the success of the total variation regularization occurs whenever the distance between the spectral components of the signal to estimate crosses a critical threshold. We prove the necessity part of this conjecture by demonstrating that TV regularization can fail bellow this limit. In addition, we enrich the sufficiency side by proposing a novel construction of a dual certificate built on top of a so-called diagonalizing basis which can guarantee a prefect reconstruction of the spectrum up to near optimal regimes.

Moreover, we study the computational cost of the TV regularization, which remains the major bottleneck to its application to practical systems. A low-dimensional semidefinite program is formulated and its equivalence with the TV approach is ensured under the existence of a certain trigonometric certificate verifying the sparse Fejér-Riesz condition, leading to potential order of magnitude changes in the computational complexity of the algorithm.

This low dimensional algorithm is then applied in the context of multirate sampling systems in order to jointly estimate sparse spectra at the output of several samplers. We demonstrate the sub-Nyquist capabilities and the high computational efficiency of such systems.