Edinburgh Research Explorer

Precise Undersampling Theorems

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions



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


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.

    Research areas

  • 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

Download statistics

No data available

ID: 582391