Computation with wavelets in higher dimensions

Abstract

In dimension $d$, a lattice grid of size $N$ has $N^d$ points. The representation of a function by, for instance, splines or the so-called non-standard wavelets with error $\varepsilon$ would require $O(\varepsilon^{-ad})$ lattice point values (resp. wavelet coefficients), for some positive $a$ depending on the spline order (resp. the properties of the wavelet). Unless $d$ is very small, we easily will get a data set that is larger than a computer in practice can handle, even for very moderate choices of $N$ or $\varepsilon$. I discuss how to organize the wavelets so that functions can be represented with $O((\log(1/\varepsilon))^{a(d- 1)}\varepsilon^{- a})$ coefficients. Using wavelet packets, the number of coefficients may be further reduced.