Université Paris 6
Pierre et Marie Curie | Université Paris 7
Denis Diderot | |

CNRS U.M.R. 7599
| ||

``Probabilités et Modèles Aléatoires''
| ||

**Auteur(s): **

**Code(s) de Classification MSC:**

- 41A25 Rate of convergence, degree of approximation
- 41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
- 65F99 None of the above but in this section
- 65N12 Stability and convergence of numerical methods
- 65N55 Multigrid methods; domain decomposition

**Résumé:** We shall present here results concerning the metric entropy of
spaces of linear and non linear approximation under very general conditions.
Our first result precises the metric entropy of the linear and non linear
approximation spaces according to an unconditional basis verifying the Temlyakov
property.
This theorem shows that the second index $r$ is not visible throughout the
behavior of the metric entropy. However, metric entropy does
discriminate between
linear and non linear approximation.
Our second result
extends and precises a result
obtained in an hilbertian framework by Donoho.
Since these theorems are given under the general context of Temlyakov
property, they
have a large spectrum of applications. For instance, it is proved in
the last
section, they can be applied, in the case of $\bL_p$ norms for $\bR^d$ for $1 < p < \infty$.
We show that the lower bounds needed for this paper are in
fact following from quite simple
large deviation inequalities concerning hypergeometric or binomial
distributions. To prove the upper bounds, we provide a
very simple
universal coding based on a
thresholding-quantizing procedure.

**Mots Clés:** *Compression ; m-term approximation ; encoding ; Kolmogorov entropy ; wavelets*

**Date:** 2001-06-07

**Prépublication numéro:** *PMA-663*