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=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 language | English (US) |
---|---|
Article number | 6086631 |
Pages (from-to) | 1010-1021 |
Number of pages | 12 |
Journal | IEEE Transactions on Signal Processing |
Volume | 60 |
Issue number | 3 |
DOIs | |
State | Published - Mar 2012 |
Keywords
- 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