This project exercises and expands upon methods for automatic discovery of new representations at multiple temporal and spatial scales. The specific framework generalizes classical harmonic analysis, in particular wavelet-based methods, to graphs and manifolds, thereby greatly extending the scope and the desirable characteristics of this multiscale-analysis framework to domains with arbitrary geometries. This framework, termed diffusion wavelets because it is associated with a diffusion process that defines the different scales, has unique properties relevant to learning, function approximation, compression and denoising. The set of core problems that this project addresses include fast algorithms for construction of multiscale diffusion wavelets, approximation of functions on very large graphs and high-dimensional manifolds, out-of-sample extensions of functions on manifolds and graphs, compression and denoising of functions on data sets, perturbation analysis, and randomized algorithms for multiscale analysis. Challenging application domains are being investigated, including analysis of document corpora, Markov decision processes, and 3D image rendering. In each case, multiscale diffusion analysis yields interpretable and meaningful results. For example, when applied to Markov decision processes, diffusion wavelet analysis yields new optimization methods that dynamically aggregate states and actions at multiple levels of abstraction; and when applied to 3D computer graphics, it yields new compression methods that capture geometric features of objects at multiple resolutions.
