Orthogonal matching pursuit: A Brownian motion analysis

Alyson K. Fletcher, Sundeep Rangan

Research output: Contribution to journalArticlepeer-review


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=2k log(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 max log(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 with a similar SNR scaling.

Original languageEnglish (US)
Article number6086631
Pages (from-to)1010-1021
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number3
StatePublished - Mar 2012


  • Compressed sensing
  • detection
  • lasso
  • orthogonal matching pursuit (OMP)
  • random matrices
  • sparse approximation
  • sparsity
  • subset selection

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Orthogonal matching pursuit: A Brownian motion analysis'. Together they form a unique fingerprint.

Cite this