Albert Cohen

Title: Matching vs. basis pursuit for approximation and learning : a comparison

Abstract:

In approximation and learning problems, one often tries to exploit an underlying sparsity property of the target function to be estimated. This property means that this function is well described as a combination of a few terms in a given dictionary. Two main class of algorithms have been developped for this purpose : basis pursuit which is based on a convex minimization procedure, and
matching pursuit in which the relevant components in the dictionary are sequentially identified. Both algorithms turn out to be equivalent in the case where the dictionary is an orthonormal basis. In this talk, their similarities and differences will be explored in the case of a general dictionary, in particular from the perspective of approximation theory.