Robust spectral compressed sensing via structured matrix completion

Yuxin Chen, Yuejie Chi

Research output: Contribution to journalArticlepeer-review

207 Scopus citations


This paper explores the problem of spectral compressed sensing, which aims to recover a spectrally sparse signal from a small random subset of its \(n\) time domain samples. The signal of interest is assumed to be a superposition of \(r\) multidimensional complex sinusoids, while the underlying frequencies can assume any continuous values in the normalized frequency domain. Conventional compressed sensing paradigms suffer from the basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this issue, we develop a novel algorithm, called enhanced matrix completion (EMaC), based on structured matrix completion that does not require prior knowledge of the model order. The algorithm starts by arranging the data into a low-rank enhanced form exhibiting multifold Hankel structure, and then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of r log4n, and is stable against bounded noise. Even if a constant portion of samples are corrupted with arbitrary magnitude, EMaC still allows exact recovery, provided that the sample complexity exceeds the order of r2log3n. Along the way, our results demonstrate the power of convex relaxation in completing a low-rank multifold Hankel or Toeplitz matrix from minimal observed entries. The performance of our algorithm and its applicability to super resolution are further validated by numerical experiments.

Original languageEnglish (US)
Article number6867345
Pages (from-to)6576-6601
Number of pages26
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 1 2014

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Robust spectral compressed sensing via structured matrix completion'. Together they form a unique fingerprint.

Cite this