Christophe Bernard, Stéphane Mallat and Jean-Jacques Slotine.
The purpose of the current research is to design a function approximation process as a multidimensional extension of usual interpolation schemes.
More precisely, we want to build a estimate F of an unknown function f on the basis of a finite number of samples (xi,yi=f(xi))i=1...n.
The algorithm wishlist is the following:
The principle consists in choosing a subset of a wavelet base adaptively, according to the locations of the pointwise samples.
The idea we want to develop to build up this subset is allocation. Each new measure (xi,yi) we take into account is allocated into a dyadic or triadic tree, like a metal ball falling down a pachinko. This is way to ensure that high resolution wavelet coefficients are used at locations where the "information" density is high enough. The main advantage of allocation is that extension of allocation as presented further in this page to higher dimensions is straightforward.
Allocation consists in affecting a new measure based on its position xi to the closest available node at a given resolution j. If this node is vacant, allocation is complete. Otherwise, there is a competition: the closest measure to the node remains, while the other is pushed down, for allocation at the next scale j+1.
Such an allocation process can be considered as a tree descent if the wavelet tree structure is triadic. The node positions and the corresponding tree structure for interpolating wavelets are displayed in Fig.1 a,b.
Fig.1 : Triadic interpolation wavelet tree structure
An example sequence of such an allocation process is displayed in Fig.2 a-d.
The allocation process is detailed in this page. NOTE however that you need a javascript enabled browser to view it.