Computation with wavelets in higher dimensions (Q1126848)

Summary: 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.