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