Share Email Print

Proceedings Paper

Approximation with highly redundant dictionaries
Author(s): Rémi Gribonval; Morten Nielsen
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Ten years ago, Mallat and Zhang proposed the Matching Pursuit algorithm : since then, the dictionary approach to signal processing has been a very active field. In this paper, we try to give an overview of a series of recent results in the field of sparse decompositions and nonlinear approximation with redundant dictionaries. We discuss sufficient conditions on a decomposition to be the unique and simultaneous sparsest ℓr expansion for all r, 0 ≤ r ≤ 1. In particular, we prove that any decomposition has this nice property if the number of its nonzero coefficients does not exceed a quantity which we call the spread of the dictionary. After a brief discussion of the interplay between sparse decompositions and nonlinear approximation with various families of algorithms, we review several recent results that provide sufficient conditions for the Matching Pursuit, Orthonormal Matching Pursuit, and Basis Pursuit algorithms to have good recovery properties. The most general conditions are not straightforward to check, but weaker estimates based on the notions of coherence of the dictionary are recalled, and we discuss how these results can be applied to approximation and sparse compositions with highly redundant incoherent dictionaries built by taking the union of several orthonormal bases. Eventually, based on Bernstein inequalities, we discuss how much approximation power can be gained by replacing a single basis with such redundant dictionaries.

Paper Details

Date Published: 13 November 2003
PDF: 12 pages
Proc. SPIE 5207, Wavelets: Applications in Signal and Image Processing X, (13 November 2003); doi: 10.1117/12.504776
Show Author Affiliations
Rémi Gribonval, IRISA (France)
Morten Nielsen, Aalborg Univ. (Denmark)

Published in SPIE Proceedings Vol. 5207:
Wavelets: Applications in Signal and Image Processing X
Michael A. Unser; Akram Aldroubi; Andrew F. Laine, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?