Sparse Recovery With Orthogonal Matching Pursuit Under RIP

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