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 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.

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

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