Compression and restoration of square integrable functions
Authors:
Rafail Krichevskii and Vladimir Potapov
Journal:
Electron. Res. Announc. Amer. Math. Soc. 2 (1996), 42-49
MSC (1991):
Primary 94A11; Secondary 42C10
DOI:
https://doi.org/10.1090/S1079-6762-96-00005-4
MathSciNet review:
1405968
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider classes of smooth functions on $[0,1]$ with mean square norm. We present a wavelet-based 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 $f$ of a class is supplied with a binary code of minimal (up to a constant factor) length, where the minimal length equals the $\varepsilon$-entropy of the class, $\varepsilon > 0$. Given that code of $f$ we can calculate $f$, $\varepsilon$-precisely in $L_2$, at any specific $N, N\geq 1,$ points of $[0,1]$ consuming $O(1+\log ^*((1/\varepsilon )^{(1/\alpha )}/N))$ operations per point. If the quantity $N$ of points is a constant, then we consume $O(\log ^*1/\varepsilon )$ operations per point. If $N$ goes up to the $\varepsilon$-entropy, then the per-point 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 $\log ^*$ is a very slowly increasing function, we can say that our calculation method is nearly optimal.
- M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, Image coding using wavelet transforms, IEEE Trans. Image Processing, 1 (1992), 205β220.
- Ingrid Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math. 41 (1988), no. 7, 909β996. MR 951745, DOI https://doi.org/10.1002/cpa.3160410705
- Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107
- Ronald A. DeVore, BjΓΆrn Jawerth, and Bradley J. Lucier, Surface compression, Comput. Aided Geom. Design 9 (1992), no. 3, 219β239. MR 1175287, DOI https://doi.org/10.1016/0167-8396%2892%2990019-L
- ---, Image compression through wavelet transform coding, IEEE Trans. Info. Theory 38 (1992), 719β746.
- Ronald A. DeVore, BjΓΆrn Jawerth, and Vasil Popov, Compression of wavelet decompositions, Amer. J. Math. 114 (1992), no. 4, 737β785. MR 1175690, DOI https://doi.org/10.2307/2374796
- 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, DOI https://doi.org/10.1006/acha.1993.1008
- A. N. Kolmogorov and V. M. Tihomirov, $\varepsilon $-entropy and $\varepsilon $-capacity of sets in function spaces, Uspehi Mat. Nauk 14 (1959), no. 2 (86), 3β86 (Russian). MR 0112032
- Rafail Krichevsky, Universal compression and retrieval, Mathematics and its Applications, vol. 274, Kluwer Academic Publishers Group, Dordrecht, 1994. MR 1282721
- 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
- Stephane G. Mallat, Multiresolution approximations and wavelet orthonormal bases of $L^2({\bf R})$, Trans. Amer. Math. Soc. 315 (1989), no. 1, 69β87. MR 1008470, DOI https://doi.org/10.1090/S0002-9947-1989-1008470-5
- 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.
- V. Rokhlin, A fast algorithm for the discrete Laplace transformation, J. Complexity 4 (1988), no. 1, 12β32. MR 939693, DOI https://doi.org/10.1016/0885-064X%2888%2990007-6
- Hans Triebel, Approximation numbers and entropy numbers of embeddings of fractional Besov-Sobolev spaces in Orlicz spaces, Proc. London Math. Soc. (3) 66 (1993), no. 3, 589β618. MR 1207550, DOI https://doi.org/10.1112/plms/s3-66.3.589
- M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, Image coding using wavelet transforms, IEEE Trans. Image Processing, 1 (1992), 205β220.
- I. Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41 (1988), 909β996.
- ---, Ten lectures on wavelets, CBMS Lecture Notes no. 61, SIAM, Philadelphia, PA, 1990.
- R. A. DeVore, B. Jawerth, and B. J. Lucier, Surface compression, Computer-Aided Geometric Design, 9 (1992), 219β239.
- ---, Image compression through wavelet transform coding, IEEE Trans. Info. Theory 38 (1992), 719β746.
- R. A. DeVore, B. Jawerth, and V. Popov, Compression of wavelet decompositions, Amer. J. Math. 114 (1992), 737β785.
- D. L. Donoho, Unconditional bases are optimal bases for data compression and statistical estimation, Applied and Computational Harmonic Analysis 1 (1993), 100β115.
- A. N. Kolmogorov and V. M. Tikhomirov, $\varepsilon$-entropy and $\varepsilon$-capacity of sets in function spaces, Uspekhi Mat. Nauk 14(1959), no. 2, 3β86. (Russian)
- R. Krichevsky, Universal compression and retrieval, Kluver Academic Publishers, 1995.
- 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. 1β10.
- S. Mallat, Multiresolution approximation and wavelet orthonormal bases of $L^2$, Trans. Amer. Math. Soc. 315 (1989), 69β87.
- 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.
- V. Rokhlin, A fast algorithm for the discrete Laplace transformation, J. of Complexity 4 (1988), 12β32.
- H. Triebel, Approximation numbers and entropy numbers of embeddings of fractional Besov-Sobolev spaces in Orlicz spaces, Proc. London Math. Soc. 66 (1993), 589β618.
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
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