Remote Access Electronic Research Announcements

Electronic Research Announcements

ISSN 1079-6762



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
MathSciNet review: 1405968
Full-text PDF

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.

References [Enhancements On Off] (What's this?)

  • [1] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, Image coding using wavelet transforms, IEEE Trans. Image Processing, 1 (1992), 205--220.
  • [2] I. Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math., 41 (1988), 909--996. 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, Computer-Aided Geometric Design, 9 (1992), 219--239. MR 93i:65029
  • [5] ------, Image compression through wavelet transform coding, IEEE Trans. Info. Theory 38 (1992), 719--746. CMP 92:11
  • [6] R. A. DeVore, B. Jawerth, and V. Popov, Compression of wavelet decompositions, Amer. J. Math. 114 (1992), 737--785. 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), 100--115. MR 94j:94011
  • [8] 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) 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. 1--10. MR 93d:65022
  • [11] S. Mallat, Multiresolution approximation and wavelet orthonormal bases of $L^2$, Trans. Amer. Math. Soc. 315 (1989), 69--87. 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), 12--32. MR 89b:65309
  • [14] 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. 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

Vladimir Potapov
Affiliation: Sobolev Mathematical Institute, Novosibirsk, Russia

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

American Mathematical Society