Archival Version
These pages are not updated anymore.
They reflect the state of
.
For the current production of this journal, please refer to
http://www.math.psu.edu/era/.
Compression and restoration of square integrable functions
This journal is archived by the American Mathematical
Society. The master copy is available at
http://www.ams.org/era/
Compression and restoration of square integrable functions
Rafail Krichevskii and Vladimir Potapov
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 the substantial 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 to the
$\varepsilon$-entropy
of the class, $ \varepsilon > 0$. Given
that code of $f$ we can $\varepsilon$-precisely in $L_2$ calculate $f$
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 \cite{11}. Since the iterated logarithm
$\log^*$ is a very slowly increasing function, we can say that our calculation
method is nearly optimal.
Copyright American Mathematical Society 1996
Retrieve entire article
Article Info
- ERA Amer. Math. Soc. 02 (1996), pp. 42-49
- Publisher Identifier: S 1079-6762(96)00005-X
- 1991 Mathematics Subject Classification. Primary 94A11;
Secondary 42C10
- Key words and phrases. Wavelets, Haar functions, compression,
computational complexity
- Received by the editors October 20, 1995, and, in revised form,
May 6, 1996
- Communicated by Ingrid Daubechies
- Comments (When Available)
Rafail Krichevskii
Sobolev Mathematical Institute,
Novosibirsk, Russia
E-mail address: rekri@math.nsc.ru
Vladimir Potapov
Sobolev Mathematical Institute,
Novosibirsk, Russia
E-mail address: rekri@math.nsc.ru
Electronic Research Announcements of the AMS Home page