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

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

Last Modified Date: 07/11/08 Last Modified By: Douglas H. Fisher Abstract 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.