Abstract

Data approximation using sparse linear expansions from overcomplete dictionaries has become a central theme in signal and image processing with applications ranging from data acquisition (compressed sensing) to denoising and compression.

For a given dictionary, we can also study best m-term approximation rates for any specific function. Interestingly, the notions of sparse expansions and certain asymptotic approximation rates are closely linked in the case of nice non-redundant dictionaries (e.g., an orthonormal basis in a Hilbert space.)

In this talk, I will explore the link between sparse expansions from an overcomplete dictionary and asymptotic approximation rates. Redundancy complicates the analysis, and we show that the close link between the two notions fails in general. However, using a probabilistic approach, we show that the close link is retained for ‘many’ redundant dictionaries.