On the exponential convergence of matching pursuits in quasi-incoherent dictionaries

被引：88

作者：

Gribonval, R

Vandergheynst, P

机构：

[1] Inst Natl Rech Informat & Automat, IRISA, F-35042 Rennes, France

[2] Ecole Polytech Fed Lausanne, Swiss Fed Inst Technol, Signal Proc Inst, CH-1015 Lausanne, Switzerland

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2006年 / 52卷 / 01期

关键词：

dictionary; greedy algorithm; matching pursuit (MP); nonlinear approximation; sparse representation;

D O I：

10.1109/TIT.2005.860474

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The purpose of this correspondence is to extend results by Villemoes and Temlyakov about exponential convergence of Matching Pursuit (MP) with some structured dictionaries for "simple" functions in finite or infinite dimension. The results are based on an extension of Tropp's results about Orthogonal Matching Pursuit (OMP) in finite dimension, with the observation that it does not only work for OMP but also for MP The main contribution is a detailed analysis of the approximation and stability properties of MP with quasi-incoherent dictionaries, and a bound on the number of steps sufficient to reach an error no larger than a penalization factor times the best m-term approximation error.

引用

页码：255 / 261

页数：7

共 30 条

[1] Atomic decomposition by basis pursuit [J].