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 Free Access

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]**Ingrid Daubechies,*Orthonormal bases of compactly supported wavelets*, Comm. Pure Appl. Math.**41**(1988), no. 7, 909–996. MR**951745**, 10.1002/cpa.3160410705**[3]**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****[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**, 10.1016/0167-8396(92)90019-L**[5]**------,*Image compression through wavelet transform coding*, IEEE Trans. Info. Theory**38**(1992), 719--746. 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**, 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**, 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****[9]**Rafail Krichevsky,*Universal compression and retrieval*, Mathematics and its Applications, vol. 274, Kluwer Academic Publishers Group, Dordrecht, 1994. MR**1282721****[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****[11]**Stephane G. Mallat,*Multiresolution approximations and wavelet orthonormal bases of 𝐿²(𝑅)*, Trans. Amer. Math. Soc.**315**(1989), no. 1, 69–87. MR**1008470**, 10.1090/S0002-9947-1989-1008470-5**[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**, 10.1016/0885-064X(88)90007-6**[14]**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**, 10.1112/plms/s3-66.3.589

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