A generalized diffusion frame for parsimonious representation of functions on data defined manifolds.

One of the now standard techniques in semi-supervised learning is to think of a high dimensional data as a subset of a low dimensional manifold embedded in a high dimensional ambient space, and to use projections of the data on eigenspaces of a diffusion map. This paper is motivated by a recent work of Coifman and Maggioni on diffusion wavelets to accomplish such projections approximately using iterates of the heat kernel. In greater generality, we consider a quasi-metric measure space X (in place of the manifold), and a very general operator T defined on the class of integrable functions on X (in place of the diffusion map). We develop a representation of functions on X in terms of linear combinations of iterates of T. Our construction obviates the need to compute the eigenvalues and eigenfunctions of the operator. In addition, the local smoothness of a function f is characterized by the local norm behavior of the terms in our representation of f. This property is similar to that of the classical wavelet representations. Although the operator T utilizes the values of the target function on the entire space, this ability results in automatic "feature detection", leading to a parsimonious representation of the target function. In the case when X is a smooth compact manifold (without boundary), our theory allows T to be any operator that commutes with the heat operator, subject to certain conditions on its eigenvalues. In particular, T can be chosen to be the heat operator itself, or a Green's operator corresponding to a suitable pseudo-differential operator.