Tree approximation and optimal encoding (Q5946561)

Wavelets are utilized in many applications including image processing and numerical methods for partial differential equations. Wavelets provide efficient decompositions of functions into simple building blocks. The authors discuss the following important question: what is the most effective way to organize the terms in the wavelet decomposition, by using tree-structures and certain ideas for nonlinear approximation [see \textit{R. A. DeVore}, Acta Numer. 7, 51-150 (1998; Zbl 0931.65007)]. The tree-structured algorithm underlying coder of \textit{J. M. Shapiro} [IEEE Trans. Signal Process. 41, No. 12, 3445-3462 (1993; Zbl 0841.94020)] is one motivation for the proposed theory. Tree approximation is a new form of nonlinear approximation which appears naturally in image processing and adaptive numerical methods. It is more restrictive than the usual \(n\)-term approximation. The restrictions of tree approximation cost little in terms of approximation rates. The authors use this method to design encoders for compression. These encoders are universal (applicable to general multivariate functions) and progressive (increasing accuracy is obtained by sending bit stream increments). The optimality of the encoders is shown in that sense that the encoders provide upper estimates for the Kolmogorov entropy of unit balls of Besov spaces.