Multiscale Wavelets on Trees, Graphs and High Dimensional Data: Theory and Applications to Semi Supervised Learning

Abstract

Harmonic analysis, and in particular the relation between function smoothnessand approximate sparsity of its wavelet coefficients, has played a key role insignal processing and statistical inference for low dimensional data. In contrast, harmonic analysis has thus far had little impact in modern problemsinvolving high dimensional data, or data encoded as graphs or networks. The main contribution of this paper is the development of a harmonic analysisapproach, including both learning algorithms and supporting theory, applicable to these moregeneral settings. Given data (be it high dimensional, graph or network) that is representedby one or more hierarchical trees, we first construct multiscale wavelet-likeorthonormal baseson it. Second, we prove that in analogyto the Euclidean case, function smoothness with respectto a specific metric induced by the tree is equivalent to exponential rate of coefficient decay, that is, to approximate sparsity. These results readily translate to simple practicalalgorithms for various learning tasks. %, such as extension from partially labeled data and function denoising. We present an application to transductive semi-supervised learning.