On the exponential convergence of matching pursuits in quasi-incoherent dictionaries
Top Cited Papers
- 27 December 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 52 (1), 255-261
- https://doi.org/10.1109/tit.2005.860474
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
This publication has 21 references indexed in Scilit:
- Recovery of Exact Sparse Representations in the Presence of Bounded NoiseIEEE Transactions on Information Theory, 2005
- Greed is Good: Algorithmic Results for Sparse ApproximationIEEE Transactions on Information Theory, 2004
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimizationProceedings of the National Academy of Sciences, 2003
- Harmonic decomposition of audio signals with matching pursuitIEEE Transactions on Signal Processing, 2003
- A generalized uncertainty principle and sparse representation in pairs of basesIEEE Transactions on Information Theory, 2002
- Weak greedy algorithms[*]This research was supported by National Science Foundation Grant DMS 9970326 and by ONR Grant N00014‐96‐1‐1003.Advances in Computational Mathematics, 2000
- Adaptive greedy approximationsConstructive Approximation, 1997
- Some remarks on greedy algorithmsAdvances in Computational Mathematics, 1996
- Analysis of sound signals with high resolution matching pursuitPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1996
- Projection Pursuit RegressionJournal of the American Statistical Association, 1981