426	RWTH Publication No: 479397        2015        IGPM426.pdf
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]