Sparse Recovery With Orthogonal Matching Pursuit Under RIP

作者：Zhang Tong^*

来源：IEEE Transactions on Information Theory, 2011, 57(9): 6215-6221.

DOI：10.1109/TIT.2011.2162263

• Estimation theory
• feature selection
• greedy algorithms
• statistical learning
• sparse recovery

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 O((kappa) over bar), then OMP can stably recover a (kappa) over bar -sparse signal in 2-norm under measurement noise. For compressed sensing applications, this result implies that in order to uniformly recover a (kappa) over bar -sparse signal in R(d), only O((kappa) over bar ln d) random projections are needed. This analysis improves some earlier results on OMP depending on stronger conditions that can only be satisfied with Omega((kappa) over bar (2) ln d) or Omega((kappa) over bar (1.6) ln d) random projections.

• 出版日期2011-9