Tree approximation and optimal encoding. (English) Zbl 0992.65151

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 R. A. DeVore, Acta Numer. 7, 51-150 (1998; Zbl 0931.65007)]. The tree-structured algorithm underlying coder of 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.


65T60 Numerical methods for wavelets
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
Full Text: DOI


[1] Adams, R. A., Sobolev Spaces (1975), Academic Press: Academic Press San Diego · Zbl 0314.46030
[2] Birgé, L.; Massard, P., An adaptive compression algorithm in Besov spaces, Constr. Approx., 16, 1-36 (2000) · Zbl 1004.41006
[3] Birman, M. S.; Solomjak, M. Z., Piecewise polynomial approximation of functions of the classes \(W_p\), Mat. Sb., 73, 295-317 (1967)
[4] Candès, E.; Donoho, D., Curvelets—A surprisingly effective nonadaptive representation for objects with edges, (Cohen, A.; Babut, C.; Schumaker, L., Curve and Surface Fihing, Saint Malo 1999 (2000), Vanderbilt Univ. Press)
[5] Cohen, A.; Daubechies, I.; Feauveau, J.-C., Biorthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math., 45, 485-560 (1992) · Zbl 0776.42020
[7] Cohen, A.; DeVore, R.; Hochmuth, R., Restricted approximation, Constr. Approx., 16, 85-113 (2000) · Zbl 0947.41006
[8] Dahlke, S.; Dahmen, W.; DeVore, R., Nonlinear approximation and adaptive techniques for solving elliptic equations, (Dahmen, W.; Kurdila, A.; Oswald, P., Multiscale Techniques for PDEs (1997), Academic Press: Academic Press San Diego), 237-284
[9] Dahlke, S.; Dahmen, W.; Hochmuth, R.; Schneider, R., Stable multiscale bases and local error estimation for elliptic problems, Appl. Numer. Math., 23, 21-47 (1997) · Zbl 0872.65098
[10] Daubechies, I., Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41, 909-996 (1988) · Zbl 0644.42026
[11] Daubechies, I., Ten Lectures on Wavelets. Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics (1992), SIAM: SIAM Philadelphia
[12] DeVore, R. A., Nonlinear approximation, Acta Numer., 7, 51-150 (1998) · Zbl 0931.65007
[13] DeVore, R. A.; Jawerth, B.; Popov, V., Compression of wavelet decompositions, Amer. J. Math., 114, 737-785 (1992) · Zbl 0764.41024
[14] DeVore, R. A.; Johnson, L. S.; Pan, C.; Sharpley, R. C., Optimal entropy encoders for mining multiply resolved data, (Ebecken, N.; Brebbia, C. A., Data Mining II (2000), MIT Press: MIT Press Boston), 73-82
[15] DeVore, R. A.; Lorentz, G. G., Constructive Approximation. Constructive Approximation, Grundlehren, 303 (1993), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0797.41016
[16] DeVore, R. A.; Sharpley, R. C., Maximal Functions Measuring Smoothness. Maximal Functions Measuring Smoothness, Memoirs of the American Mathematical Society, 293 (1984), Am. Math. Soc: Am. Math. Soc Providence · Zbl 0529.42005
[17] Donoho, D., Unconditional bases and bit-level compression, Appl. Comput. Harmon. Anal., 3, 388-392 (1996) · Zbl 0936.62004
[18] Mallat, S.; Falzon, F., Analysis of low bit rate transform coding, IEEE Trans. Signal Process., 46, 1027-1042 (1998)
[19] Güntürk, C., Harmonic Analysis of Two Problems in Signal Analysis and Compression (2000), Princeton University: Princeton University Princeton
[20] Lorentz, G. G.; von Golitschek, M.; Makovoz, Ju., Constructive Approximation: Advanced Problems (1996), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0910.41001
[21] Said, A.; Pearlman, W. A., An image multyresolution representation for lossless and lossy compression, IEEE Trans. Image Process., 5, 1303-1310 (1996)
[22] Shapiro, J., Embedded image coding using zero-trees of wavelet coefficients, IEEE Trans. Signal Process., 41, 3445-3462 (1993) · Zbl 0841.94020
[23] Temlyakov, V., Best \(m\)-term approximation and greedy algorithms, Adv. Comput. Math., 8, 249-265 (1998) · Zbl 0905.65063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.