An Adaptive Compression Algorithm in Besov Spaces

A new algorithm providing an approximation $\tilde f of f with a prescribed number D of nonzero coefficients in its expansion with the optimal rate D-α of approximation with respect to the Lq -norm when f belongs to some Besov space Bαp,∈fty whenever α>(1/p-1/q)+ .

Abstract

Given a function f on [0,1] and a wavelet-type expansion of f , we introduce a new algorithm providing an approximation $\tilde f of f with a prescribed number D of nonzero coefficients in its expansion. This algorithm depends only on the number of coefficients to be kept and not on any smoothness assumption on f . Nevertheless it provides the optimal rate D -α of approximation with respect to the L q -norm when f belongs to some Besov space B α p,∈fty whenever α>(1/p-1/q) + . These results extend to more general expansions including splines and piecewise polynomials and to multivariate functions. Moreover, this construction allows us to compute easily the metric entropy of Besov balls.