Approximation with highly redundant dictionaries

Publisher Website
Google Scholar
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.

This publication has 0 references indexed in Scilit: