Orthogonal Matching Pursuit Under the Restricted Isometry Property Academic Article uri icon


  • © 2016, Springer Science+Business Media New York. This paper is concerned with the performance of orthogonal matching pursuit (OMP) algorithms applied to a dictionary D in a Hilbert space H. Given an element f∈ H, OMP generates a sequence of approximations fn, n= 1 , 2 , … , each of which is a linear combination of n dictionary elements chosen by a greedy criterion. It is studied whether the approximations fn are in some sense comparable to best n-term approximation from the dictionary. One important result related to this question is a theorem of Zhang (IEEE Trans Inf Theory 57(9):6215–6221, 2011) in the context of sparse recovery of finite dimensional signals. This theorem shows that OMP exactly recovers n-sparse signals with at most An iterations, provided the dictionary D satisfies a restricted isometry property (RIP) of order An for some constant A, and that the procedure is also stable in ℓ2 under measurement noise. The main contribution of the present paper is to give a structurally simpler proof of Zhang’s theorem, formulated in the general context of n-term approximation from a dictionary in arbitrary Hilbert spaces H. Namely, it is shown that OMP generates near best n-term approximations under a similar RIP condition.

author list (cited authors)

  • Cohen, A., Dahmen, W., & DeVore, R.

citation count

  • 20

publication date

  • February 2017