Title :
On the exponential convergence of matching pursuits in quasi-incoherent dictionaries
Author :
Gribonval, Rémi ; Vandergheynst, Pierre
Author_Institution :
IRISA/INRIA, France
Abstract :
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.
Keywords :
approximation theory; greedy algorithms; image processing; iterative methods; numerical stability; sparse matrices; time-frequency analysis; OMP; approximation error; exponential convergence; finite dimension; greedy algorithm; nonlinear approximation; orthogonal matching pursuit; quasiincoherent dictionary; sparse representation; stability property; Convergence; Dictionaries; Greedy algorithms; Hilbert space; Iterative algorithms; Matching pursuit algorithms; Pursuit algorithms; Signal processing; Signal processing algorithms; Signal synthesis; Dictionary; greedy algorithm; matching pursuit (MP); nonlinear approximation; sparse representation;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2005.860474
