You are here

  1. Home
  2. » Forschung
  3. » Preprints
Preprint-No.: <   426   >   Published in: June 2015   PDF-File: IGPM426.pdf
Title:Orthogonal Matching Pursuit under the Restricted Isometry Property
Authors:Albert Cohen, Wolfgang Dahmen and Ronald DeVore
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 [math.NA]