Université Paris 6Pierre et Marie Curie Université Paris 7Denis Diderot CNRS U.M.R. 7599 Probabilités et Modèles Aléatoires''

### Entropy, universal coding, approximation and bases properties

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