Precise Undersampling Theorems

David L. Donoho, Jared Tanner

Research output: Contribution to journalArticlepeer-review

Abstract

Undersampling theorems state that we may gather far fewer samples than the usual sampling theorem while exactly reconstructing the object of interest-provided the object in question obeys a sparsity condition, the samples measure appropriate linear combinations of signal values, and we reconstruct with a particular nonlinear procedure. While there are many ways to crudely demonstrate such under-sampling phenomena, we know of only one mathematically rigorous approach which precisely quantifies the true sparsity-undersampling tradeoff curve of standard algorithms and standard compressed sensing matrices. That approach, based on combinatorial geometry, predicts the exact location in sparsity-undersampling domain where standard algorithms exhibit phase transitions in performance. We review the phase transition approach here and describe the broad range of cases where it applies. We also mention exceptions and state challenge problems for future research. Sample result: one can efficiently reconstruct a k-sparse signal of length N from n measurements, provided n greater than or similar to 2k . log(N/n), for (k, n, N) large, k << N. AMS 2000 subject classifications. Primary: 41A46, 52A22, 52B05, 62E20, 68P30, 94A20; Secondary: 15A52, 60F10, 68P25, 90C25, 94B20.

Original languageEnglish
Pages (from-to)913-924
Number of pages12
JournalProceedings of the IEEE
Volume98
Issue number6
DOIs
Publication statusPublished - Jun 2010

Keywords

  • Bandlimited measurements
  • compressed sensing
  • l(1)-minimization
  • random measurements
  • random polytopes
  • superresolution
  • undersampling
  • universality of matrix ensembles
  • UNCERTAINTY PRINCIPLES
  • SIGNAL RECONSTRUCTION
  • SPARSE REPRESENTATION
  • POLYTOPES
  • RECOVERY
  • NEIGHBORLINESS
  • MINIMIZATION
  • SIMPLICES
  • EQUATIONS
  • DIMENSION

Cite this