RI-Medium: Collaborative Research: Learning Multiscale Representations using Harmonic Analysis on Graphs

本项目练习并扩展了在多个时间和空间尺度上自动发现新表示的方法。该框架将经典的调和分析，特别是基于小波的方法推广到图形和流形上，从而极大地扩展了这种多尺度分析框架的范围和理想的特征，使其适用于具有任意几何形状的区域。这种框架被称为扩散小波，因为它与定义不同尺度的扩散过程相关联，具有与学习、函数逼近、压缩和去噪相关的独特性质。该项目解决的一组核心问题包括构造多尺度扩散小波的快速算法、非常大的图和高维流形上函数的逼近、流形和图上函数的样本外扩展、数据集上函数的压缩和去噪、扰动分析以及用于多尺度分析的随机化算法。正在研究具有挑战性的应用领域，包括文档语料库分析、马尔可夫决策过程和3D图像渲染。在每种情况下，多尺度扩散分析都会产生可解释和有意义的结果。例如，当应用于马尔可夫决策过程时，扩散小波分析产生了在多个抽象层次上动态聚集状态和动作的新的优化方法；当应用于3D计算机图形学时，它产生了以多个分辨率捕捉对象的几何特征的新的压缩方法。

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.