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 Calderòn-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.