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

Abstract | References | Similar Articles | Additional Information

Abstract: We consider classes of smooth functions on 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 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 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 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), 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,*-entropy and -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*, 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**

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:
https://doi.org/10.1090/S1079-6762-96-00005-4

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