426 IGPM426.pdf        June 2015
TITLE Orthogonal Matching Pursuit under the Restricted Isometry Property
AUTHORS Albert Cohen, Wolfgang Dahmen, Ronald DeVore
ABSTRACT 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 f n , 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 f n 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 [8] in the context of sparse recovery of finite dimensional signals. This theorem shows that OMP exactly recovers n-sparse signal, whenever the dictionary D satisfies a Restricted Isometry Property (RIP) of order An for some constant A, and that the procedure is also stable in l 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.
KEYWORDS orthogonal matching pursuit, best n term approximation, instance optimality, restricted isometry property
DOI 10.1007/s00365-016-9338-2
PUBLICATION Constructive Approximation
45 (no.1) (2017), 113–127

http://arxiv.org/abs/1506.04779 [math.NA]