Skip to Main Content
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
DOI: https://doi.org/10.1090/S1079-6762-96-00005-4
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
Email: rekri@math.nsk.su

Vladimir Potapov
Affiliation: Sobolev Mathematical Institute, Novosibirsk, Russia
Email: rekri@math.nsk.su

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