Orthogonal Matching Pursuit Under the Restricted Isometry Property

详细信息    查看全文

• 作者：Albert Cohen ; Wolfgang Dahmen ; Ronald DeVore
• 关键词：Orthogonal matching pursuit ; Best n ; term approximation ; Instance optimality ; Restricted isometry property
• 刊名：Constructive Approximation
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：45
• 期：1
• 页码：113-127
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Numerical Analysis; Analysis;
• 出版者：Springer US
• ISSN：1432-0940
• 卷排序：45

文摘

This paper is concerned with the performance of orthogonal matching pursuit (OMP) algorithms applied to a dictionary \(\mathcal{D}\) in a Hilbert space \(\mathcal{H}\). Given an element \(f\in \mathcal{H}\), OMP generates a sequence of approximations \(f_n\), \(n=1,2,\ldots \), 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 (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 \(\mathcal{D}\) satisfies a restricted isometry property (RIP) of order An for some constant A, and that the procedure is also stable in \(\ell ^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 \(\mathcal{H}\). Namely, it is shown that OMP generates near best n-term approximations under a similar RIP condition.