Sparse Recovery With Orthogonal Matching Pursuit Under RIP

By Tong Zhang. IEEE Transactions on Information Theory, 2010

385 citations recorded by the source corpus.

This paper presents a new analysis for the orthogonal matching pursuit (OMP) algorithm. It is shown that if the restricted isometry property (RIP) is satisfied at sparsity level <i>O</i>(k̅), then OMP can stably recover a <i>k̅</i>-sparse signal in 2-norm under measurement noise. For compressed sensing applications, this result implies that in order to uniformly recover a <i>k̅</i>-sparse signal in R<i>d</i>, only <i>O</i>(<i>k̅</i> ln<i>d</i>) random projections are needed. This analysis improves some earlier results on OMP depending on stronger conditions that can only be satisfied with Ω(<i>k̅</i>² ln<i>d</i>) or Ω(<i>k̅</i>^1.6 ln<i>d</i>) random projections.

Subfields: Acoustics and Ultrasonics, Biomedical Engineering, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/4e785eea95b781145b3af9873053bada4496d1bd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Acoustics and Ultrasonics

1. Yonina C. Eldar
2. Byonghyo Shim
3. Sahand N. Negahban
4. Riki Eto
5. A. Dimakis
6. Ryohei Fujimaki
7. Marco F. Duarte
8. Jian Wang

In Biomedical Engineering

1. Marco F. Duarte
2. Yonina C. Eldar
3. Bhaskar D. Rao
4. Liefeng Bo
5. Dieter Fox
6. Byonghyo Shim
7. Sahand N. Negahban
8. Riki Eto

In Computational Mechanics

1. Yonina C. Eldar
2. Marco F. Duarte
3. Bhaskar D. Rao
4. Zhilin Zhang
5. Dieter Fox
6. A. Dimakis
7. Byonghyo Shim
8. Dong In Kim

Citations in the corpus

• Fully-Automatic Bayesian Piecewise Sparse Linear Models (2014, methodology): “We solve the L0-regularized feature selection problem (17) by applying the forward backward greedy (FoBa) algorithm [7, 8] since it offers the tightest upper bounds of feature selection error, estimation error, and objective error.”
• Restricted Strong Convexity Implies Weak Submodularity (2016, result): “Focusing explicitly on OMP, most previous results require the strong RIP assumption (such as in Corollary 2 of [12]), whereas we only require the weaker RSC and RSM assumptions.”
• Structured Compressed Sensing: From Theory to Applications (2011, background): “Theorem 9 [64]: Let the signal and write .”
• Generalized Orthogonal Matching Pursuit (2011, result): “It should also be noted that by allowin g more iterations (larger thanK iterations) for the OMP, one can improve performance [20], [24], [25] and achieve performance comparable to the gOMP.”
• Compressed Sensing for Wireless Communications: Useful Tips and Tricks (2015, background): “Note that RIP is useful to analyze performance when the measu r ments are contaminated by the noise [5], [20]–[22].”
• Learning hierarchical sparse features for RGB-(D) object recognition (2014, background): “In the past few years, there has been significant interest in theoretical analysis of the OMP algorithm (Tropp and Gilbert, 2007; Jain et al., 2011; Zhang, 2011).”