Orthogonal matching pursuit from noisy measurements: A new analysis

Alyson K. Fletcher, Sundeep Rangan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A well-known analysis of Tropp and Gilbert shows that orthogonal matching pursuit (OMP) can recover a k-sparse n-dimensional real vector from m = 4k log(n) noise-free linear measurements obtained through a random Gaussian measurement matrix with a probability that approaches one as n → ∞. This work strengthens this result by showing that a lower number of measurements, m = 2klog(n - k), is in fact sufficient for asymptotic recovery. More generally, when the sparsity level satisfies k min ≤ k ≤ k max but is unknown, m = 2k maxlog(n - k min) measurements is sufficient. Furthermore, this number of measurements is also sufficient for detection of the sparsity pattern (support) of the vector with measurement errors provided the signal-to-noise ratio (SNR) scales to infinity. The scaling m = 2k log(n - k) exactly matches the number of measurements required by the more complex lasso method for signal recovery in a similar SNR scaling.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference
Pages540-548
Number of pages9
StatePublished - 2009
Event23rd Annual Conference on Neural Information Processing Systems, NIPS 2009 - Vancouver, BC, Canada
Duration: Dec 7 2009Dec 10 2009

Publication series

NameAdvances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference

Other

Other23rd Annual Conference on Neural Information Processing Systems, NIPS 2009
CountryCanada
CityVancouver, BC
Period12/7/0912/10/09

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Orthogonal matching pursuit from noisy measurements: A new analysis'. Together they form a unique fingerprint.

Cite this