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 XX (in place of the manifold), and a very general operator TT defined on the class of integrable functions on XX (in place of the diffusion map). We develop a representation of functions on XX in terms of linear combinations of iterates of TT. Our construction obviates the need to compute the eigenvalues and eigenfunctions of the operator. In addition, the local smoothness of a function ff is characterized by the local norm behavior of the terms in our representation of ff. This property is similar to that of the classical wavelet representations. Although the operator TT 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 XX is a smooth compact manifold (without boundary), our theory allows TT to be any operator that commutes with the heat operator, subject to certain conditions on its eigenvalues. In particular, TT can be chosen to be the heat operator itself, or a Green’s operator corresponding to a suitable pseudo-differential operator.