Tree approximation and optimal encoding. (English) Zbl 0992.65151

Cohen, Albert; Dahmen, Wolfgang; Daubechies, Ingrid; DeVore, Ronald

Appl. Comput. Harmon. Anal. 11, No. 2, 192-226 (2001).

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.

Reviewer: Manfred Tasche (Rostock)

MSC:

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

Keywords:

tree approximation; nonlinear approximation; \(n\)-term approximation; optimal encoding; data compression; wavelet decomposition; tree-structured algorithm; image processing; adaptive numerical method; Kolmogorov entropy

References:

[1]	Adams, R.A., Sobolev spaces, (1975), 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 Wp, Mat. sb., 73, 295-317, (1967)
[4]	Candès, E.; Donoho, D., Curvelets—A surprisingly effective nonadaptive representation for objects with edges, ()
[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
[6]	A. Cohen, I. Daubechies, O. Guleryuz, and, M. Orchard, On the importance of combining wavelet based non-linear approximation in coding strategies, IEEE Trans. Inf. Th, in press. · Zbl 1061.94004
[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, (), 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, CBMS-NSF regional conference series in applied mathematics, (1992), 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, (), 73-82
[15]	DeVore, R.A.; Lorentz, G.G., Constructive approximation, Grundlehren, 303, (1993), Springer-Verlag Berlin/New York · Zbl 0797.41016
[16]	DeVore, R.A.; Sharpley, R.C., Maximal functions measuring smoothness, Memoirs of the American mathematical society, 293, (1984), Am. Math. Soc Providence
[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
[20]	Lorentz, G.G.; von Golitschek, M.; Makovoz, Ju., Constructive approximation: advanced problems, (1996), 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