Approximation with highly redundant dictionaries

Rémi Gribonval; Morten Nielsen

doi:10.1117/12.504776

13 November 2003 Approximation with highly redundant dictionaries

Rémi Gribonval, Morten Nielsen

Proceedings Volume 5207, Wavelets: Applications in Signal and Image Processing X; (2003) https://doi.org/10.1117/12.504776
Event: Optical Science and Technology, SPIE's 48th Annual Meeting, 2003, San Diego, California, United States

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.

Citation Download Citation

Rémi Gribonval and Morten Nielsen "Approximation with highly redundant dictionaries", Proc. SPIE 5207, Wavelets: Applications in Signal and Image Processing X, (13 November 2003); https://doi.org/10.1117/12.504776

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available