Title: Diffusion Wavelets for multiscale analysis on manifolds and 
graphs: constructions and applications.



Abstract:
The study of diffusion operators of manifolds, graphs and data has many
applications to the analysis of the structure of the underlying space
and of functions on the space. This has applications to data analysis,
clustering, learning, and partial differential equations.
Given a local operator T on a manifold or a graph, with large powers of
low rank, we present a general multiresolution construction for
efficiently computing, representing and compressing T^t. This allows the
computation, to high precision, of functions of the operator, notably
the associated Green's functions, in compressed form, and their fast
application. Classes of operators for which these computations are fast
include certain diffusion-like operators, in any dimension, on
manifolds, graphs, and in non-homogeneous media.
Our construction can be viewed as a generalization of some Fast
Multipole Methods, achieved through a different point of view, and of
the non-standard wavelet representation of Caldern-Zygmund and
pseudodifferential operators, achieved through a different
multiresolution analysis adapted to the operator. It is also related to
algebraic multigrid techinques (without grids), but has high-precision
and no cycles.
The dyadic powers of an operator can be used to induce a multiresolution
analysis, as in classical Littlewood-Paley and wavelet theory, and we
construct, with fast and stable algorithms, orthonormal scaling function
and wavelet bases associated to this multiresolution analysis, together
with the corresponding downsampling operators, and use them to compress
the corresponding powers of the operator.
This allows to extend multiscale signal processing to general spaces
(such as manifolds and graphs) in a very natural way, with corresponding
fast algorithms.
Applications include function approximation, denoising, and learning on
data sets, clustering of data sets, multiscale analysis of Markov chains
and of complex networks, mesh and texture compression in 3D computer
graphics.