We introduce a framework for representing functions defined on high-dimensional data. In this framework, we propose to use the eigenvectors of the graph Laplacian
to construct a multiresolution analysis on the data. This results in a one parameter family of orthogonal bases, which includes both Haar basis as well as the eigenvectors of the graph Laplacian. We describe a discrete fast transform for expansion in any of the bases in this family, and derive an asymptotic rate of coefficients decay. The question of measuring the smoothness of discrete functions is also addressed based on a discrete analogue of Besov spaces. We demonstrate our construction using several numerical examples and an application of the proposed bases to the compression of hyperspectral images.
This is a joint work with Yoel Shkolnisky.