On the exponential convergence of matching pursuits in quasi-incoherent dictionaries
The purpose of this paper is to extend results by Villemoes about exponential convergence of Matching Pursuit with some structured dictionaries for simple functions in finite or infinite dimension. Our results are based on an extension of Tropp s results about Orthogonal Matching Pursuit in finite dimension, with the observation that it does not only work for OMP but also for MP. Our 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.
Gribonval2004_1160.pdf
openaccess
190.98 KB
Adobe PDF
285f09d7b7013601ce4f1cf292a772ba