A class of Laplacian multiwaveleth bases for high-dimensional data

作者：Sharon Nir^*; Shkolnisky Yoel

来源：Applied and Computational Harmonic Analysis, 2015, 38(3): 420-451.

DOI：10.1016/j.acha.2014.07.002

• High dimensional data
• Graph Laplacian
• Multiwavelets
• Multiresolution analysis

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. We assume the dataset to have an associated hierarchical tree partition, together with a function that measures the similarity between pairs of points in the dataset. The construction results in a one parameter family of orthonormal bases, which includes both the Haar basis as well as the eigenvectors of the graph Laplacian, as its two extremes. We describe a fast discrete transform for the expansion in any of the bases in this family, and estimate the decay rate of the expansion coefficients. We also bound the error of non-linear approximation of functions in our bases. The properties of our construction are demonstrated using various numerical examples.

• 出版日期2015-5