Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

This journal is archived by the American Mathematical Society. The master copy is available at http://www.ams.org/era/

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

TeX source (28K)
DVI (38K)
PostScript (134K)

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