Compression and restoration of square integrable functions
Authors:
Rafail Krichevskii and Vladimir Potapov
Journal:
Electron. Res. Announc. Amer. Math. Soc. 2 (1996), 4249
MSC (1991):
Primary 94A11; Secondary 42C10
MathSciNet review:
1405968
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We consider classes of smooth functions on with mean square norm. We present a waveletbased method for obtaining approximate pointwise reconstruction of every function with nearly minimal cost without substantially increasing the amount of data stored. In more detail: each function of a class is supplied with a binary code of minimal (up to a constant factor) length, where the minimal length equals the entropy of the class, . Given that code of we can calculate , precisely in , at any specific points of consuming operations per point. If the quantity of points is a constant, then we consume operations per point. If goes up to the entropy, then the perpoint time consumption goes down to a constant, which is less than the corresponding constant in the fast algorithm of Mallat [11]. Since the iterated logarithm is a very slowly increasing function, we can say that our calculation method is nearly optimal.
 [1]
M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, Image coding using wavelet transforms, IEEE Trans. Image Processing, 1 (1992), 205220.
 [2]
Ingrid
Daubechies, Orthonormal bases of compactly supported wavelets,
Comm. Pure Appl. Math. 41 (1988), no. 7,
909–996. MR
951745 (90m:42039), http://dx.doi.org/10.1002/cpa.3160410705
 [3]
Ingrid
Daubechies, Ten lectures on wavelets, CBMSNSF Regional
Conference Series in Applied Mathematics, vol. 61, Society for
Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107
(93e:42045)
 [4]
Ronald
A. DeVore, Björn
Jawerth, and Bradley
J. Lucier, Surface compression, Comput. Aided Geom. Design
9 (1992), no. 3, 219–239. MR 1175287
(93i:65029), http://dx.doi.org/10.1016/01678396(92)90019L
 [5]
, Image compression through wavelet transform coding, IEEE Trans. Info. Theory 38 (1992), 719746. CMP 92:11
 [6]
Ronald
A. DeVore, Björn
Jawerth, and Vasil
Popov, Compression of wavelet decompositions, Amer. J. Math.
114 (1992), no. 4, 737–785. MR 1175690
(94a:42045), http://dx.doi.org/10.2307/2374796
 [7]
David
L. Donoho, Unconditional bases are optimal bases for data
compression and for statistical estimation, Appl. Comput. Harmon.
Anal. 1 (1993), no. 1, 100–115. MR 1256530
(94j:94011), http://dx.doi.org/10.1006/acha.1993.1008
 [8]
A.
N. Kolmogorov and V.
M. Tihomirov, 𝜖entropy and 𝜖capacity of sets in
function spaces, Uspehi Mat. Nauk 14 (1959),
no. 2 (86), 3–86 (Russian). MR 0112032
(22 #2890)
 [9]
Rafail
Krichevsky, Universal compression and retrieval, Mathematics
and its Applications, vol. 274, Kluwer Academic Publishers Group,
Dordrecht, 1994. MR 1282721
(95g:94006)
 [10]
Tom
Lyche and Larry
L. Schumaker (eds.), Mathematical methods in computer aided
geometric design. II, Academic Press, Inc., Boston, MA, 1992. Papers
from the International Conference on Curves, Surfaces, CAGD, and Image
Processing held in Biri, June 20–25, 1991. MR 1172789
(93d:65022)
 [11]
Stephane
G. Mallat, Multiresolution approximations and
wavelet orthonormal bases of 𝐿²(𝑅), Trans. Amer. Math. Soc. 315 (1989), no. 1, 69–87. MR 1008470
(90e:42046), http://dx.doi.org/10.1090/S00029947198910084705
 [12]
V. Pan, J. Reif, and S. Tate, The power of combining the techniques of algebraic and numerical computing: improved approximate multipoint polynomial evaluation and improved multipole algorithms (Proc. of 33 Annual Symp. on Found. of Comp. Sc.), IEEE Comp. Soc. Press, Pittsburgh, 1992.
 [13]
V.
Rokhlin, A fast algorithm for the discrete Laplace
transformation, J. Complexity 4 (1988), no. 1,
12–32. MR
939693 (89b:65309), http://dx.doi.org/10.1016/0885064X(88)900076
 [14]
Hans
Triebel, Approximation numbers and entropy numbers of embeddings of
fractional BesovSobolev spaces in Orlicz spaces, Proc. London Math.
Soc. (3) 66 (1993), no. 3, 589–618. MR 1207550
(94g:46042), http://dx.doi.org/10.1112/plms/s366.3.589
 [1]
 M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, Image coding using wavelet transforms, IEEE Trans. Image Processing, 1 (1992), 205220.
 [2]
 I. Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41 (1988), 909996. MR 90m:42039
 [3]
 , Ten lectures on wavelets, CBMS Lecture Notes no. 61, SIAM, Philadelphia, PA, 1990. MR 93e:42045
 [4]
 R. A. DeVore, B. Jawerth, and B. J. Lucier, Surface compression, ComputerAided Geometric Design, 9 (1992), 219239. MR 93i:65029
 [5]
 , Image compression through wavelet transform coding, IEEE Trans. Info. Theory 38 (1992), 719746. CMP 92:11
 [6]
 R. A. DeVore, B. Jawerth, and V. Popov, Compression of wavelet decompositions, Amer. J. Math. 114 (1992), 737785. MR 94a:42045
 [7]
 D. L. Donoho, Unconditional bases are optimal bases for data compression and statistical estimation, Applied and Computational Harmonic Analysis 1 (1993), 100115. MR 94j:94011
 [8]
 A. N. Kolmogorov and V. M. Tikhomirov, entropy and capacity of sets in function spaces, Uspekhi Mat. Nauk 14(1959), no. 2, 386. (Russian) MR 22:2890
 [9]
 R. Krichevsky, Universal compression and retrieval, Kluver Academic Publishers, 1995. MR 95g:94006
 [10]
 B. J. Lucier, Wavelets and image compression, Mathematical Methods in CAGD and Image Processing (T. Lyche and L.L. Schumaker, eds.), Academic Press, Boston, MA, 1992, pp. 110. MR 93d:65022
 [11]
 S. Mallat, Multiresolution approximation and wavelet orthonormal bases of , Trans. Amer. Math. Soc. 315 (1989), 6987. MR 90e:42046
 [12]
 V. Pan, J. Reif, and S. Tate, The power of combining the techniques of algebraic and numerical computing: improved approximate multipoint polynomial evaluation and improved multipole algorithms (Proc. of 33 Annual Symp. on Found. of Comp. Sc.), IEEE Comp. Soc. Press, Pittsburgh, 1992.
 [13]
 V. Rokhlin, A fast algorithm for the discrete Laplace transformation, J. of Complexity 4 (1988), 1232. MR 89b:65309
 [14]
 H. Triebel, Approximation numbers and entropy numbers of embeddings of fractional BesovSobolev spaces in Orlicz spaces, Proc. London Math. Soc. 66 (1993), 589618. MR 94g:46042
Similar Articles
Retrieve articles in Electronic Research Announcements of the American Mathematical Society
with MSC (1991):
94A11,
42C10
Retrieve articles in all journals
with MSC (1991):
94A11,
42C10
Additional Information
Rafail Krichevskii
Affiliation:
Sobolev Mathematical Institute, Novosibirsk, Russia
Email:
rekri@math.nsk.su
Vladimir Potapov
Affiliation:
Sobolev Mathematical Institute, Novosibirsk, Russia
Email:
rekri@math.nsk.su
DOI:
http://dx.doi.org/10.1090/S1079676296000054
PII:
S 10796762(96)000054
Keywords:
Wavelets,
Haar functions,
compression,
computational complexity
Received by editor(s):
October 20, 1995
Received by editor(s) in revised form:
May 6, 1996
Communicated by:
Ingrid Daubechies
Article copyright:
© Copyright 1996
American Mathematical Society
