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 $\epsilon$ would require $O({\epsilon }^{-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 $\epsilon$. I discuss how to organize the wavelets so that functions can be represented with $O((\log (1/\epsilon ){)}^{a(d-1)}{\epsilon }^{-a})$ coefficients. Using wavelet packets, the number of coefficients may be further reduced.