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

Carlos Fernandez-Granda, Gongguo Tang, Xiaodong Wang, Le Zheng

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)105-168
Number of pages64
JournalInformation and Inference
Volume7
Issue number1
DOIs
StatePublished - 2018

Keywords

  • Atomic norm
  • Continuous dictionary
  • Convex optimization
  • Greedy methods
  • Line spectra estimation
  • Outliers
  • Semi-definite programming
  • Sparse recovery
  • Super-resolution

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Analysis
  • Applied Mathematics
  • Statistics and Probability
  • Numerical Analysis

Fingerprint Dive into the research topics of 'Demixing sines and spikes: Robust spectral super-resolution in the presence of outliers'. Together they form a unique fingerprint.

Cite this