Demixing sines and spikes: Robust spectral super-resolution in the presence of outliers

We consider the problem of super-resolving the line spectrum of a multisinusoidal signal from a finite number of samples, some of which may be completely corrupted. Measurements of this form can be modeled as an additive mixture of a sinusoidal and a sparse component. We propose to demix the two components and super-resolve the spectrum of the multisinusoidal signal by solving a convex program. Our main theoretical result is that-up to logarithmic factors-this approach is guaranteed to be successful with high probability for a number of spectral lines that is linear in the number of measurements, even if a constant fraction of the data are outliers. The result holds under the assumption that the phases of the sinusoidal and sparse components are random and the line spectrum satisfies a minimum-separation condition. We show that the method can be implemented via semi-definite programming, and explain how to adapt it in the presence of dense perturbations as well as exploring its connection to atomic-norm denoising. In addition, we propose a fast greedy demixing method that provides good empirical results when coupled with a local non-convex-optimization step.