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

CNRS U.M.R. 7599
``Probabilités et Modèles Aléatoires''

Entropy, universal coding, approximation and bases properties


Code(s) de Classification MSC:

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