Entropy,Universal Coding,Approximation, and Bases Properties

We shall present here results concerning the metric entropy of spaces of linear and nonlinear approximation under very general conditions. Our first result computes the metric entropy of the linear and m-terms approximation classes according to a quasi-greedy 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 nonlinear approximation. Our second result extends and refines a result obtained in a Hilbertian framework by Donoho, proving that under orthosymmetry conditions, m-terms approximation classes are characterized by the metric entropy. Since these theorems are given under the general context of quasi-greedy bases verifying the Temlyakov property, they have a large spectrum of applications. For instance, it is proved in the last section that they can be applied in the case of L _p norms for R ^d for 1 < p < \infty. We show that the lower bounds needed for this paper in fact follow 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 constructive procedure.