Computation with wavelets in higher dimensions

  • Jan-Olov Strömberg


In dimension dd, a lattice grid of size NN has NdN^d points. The representation of a function by, for instance, splines or the so-called non-standard wavelets with error ε\varepsilon would require O(εad)O(\varepsilon^{-ad}) lattice point values (resp. wavelet coefficients), for some positive aa depending on the spline order (resp. the properties of the wavelet). Unless dd 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 NN or ε\varepsilon. I discuss how to organize the wavelets so that functions can be represented with O((log(1/ε))a(d1)εa)O((\log(1/\varepsilon))^{a(d- 1)}\varepsilon^{- a}) coefficients. Using wavelet packets, the number of coefficients may be further reduced.