Orthogonal Matching Pursuit Under the Restricted Isometry Property
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
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):62156221, 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 Zhangs 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.
