The problem

We are given a set of N data points in high dimensional Euclidean space, and a kernel such that a graph on the data points is well-defined. We also assume the set of data points has an associated tree structure (hierarchy tree).

Our aim is to construct an orthonormal basis, defined on the set of data points, that satisfies:

1 - The construction must be applicable in cases where the dimension fo the data is very large.

2 - It should allow for a sparse representation of a large family of functions.

3 - It must have a fast and numerically stable algorithm.

Known solutions (partial list)

1 - Eigenvectors of the graph laplacian. For example, see here.

2 - Haar-like basis (Gavish, Nadler, and Coifman).

3 - Construction in spaces of homogeneous type (Auscher and Hytonen).

4 - Diffusion wavelets. see here.

Our solution

We suggest a family of bases, named Laplacian MultiWavelets (LMW). Our basic tool is the graph laplacian and its eigenvectors, combined with the hierarchy tree on the data.

This family is parameterized by one integer parameter, range between one and the number of data points. This parameter sets the number of vanishing moments (related to the decay rate of the expansion coefficients), and the locality of the elements.

For parameter equal to one we simply gets the Haar-like basis, having only one vanishing moments (i.e., orthogonal only to constant functions) but highly local. Choosing the maximum parameter value yields the basis of eigenvectors of the graph laplacian (Fourier bases on the data). Any parameter value in between leads to intermediate resulted bases.

We have fast and stable implementations, and a variety of numerical examples and scripts (see next). We also proved approximation rates and smoothness analysis of functions defined on the data set, using the LMW basis.

The paper. In press (ACHA journal).

Some illustrations

Multiscaling: a few elements, data points on the real line.

The pixels of the upper right image is our data. Counterclockwise are the elements of the basis, depend on the geometry of the data and become more local.

Locality: overview of the support of the basis elements, presented as matrix columns. ‘k’ is the algorithm parameter.

Compressing hyper-spectral images: the compression of the surface temperature using LMW vs two popular compression of DCT (cosines transform) and JPG2000 (wavelets). The LMW has as data a spectral image consisting of 12 vision frequencies (details in the paper above)