Math @ Duke

Publications [#243833] of Mauro Maggioni
Papers Published
 Coifman, RR; Maggioni, M, Diffusion wavelets,
Applied and Computational Harmonic Analysis, vol. 21 no. 1
(July, 2006),
pp. 5394, ISSN 10635203 [doi]
(last updated on 2018/10/21)
Abstract: Our goal in this paper is to show that many of the tools of signal processing, adapted Fourier and wavelet analysis can be naturally lifted to the setting of digital data clouds, graphs, and manifolds. We use diffusion as a smoothing and scaling tool to enable coarse graining and multiscale analysis. Given a diffusion 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 Tt. This allows a direct multiscale computation, to high precision, of functions of the operator, notably the associated Green's function, in compressed form, and their fast application. Classes of operators for which these computations are fast include certain diffusionlike operators, in any dimension, on manifolds, graphs, and in nonhomogeneous media. We use ideas related to the Fast Multipole Methods and to the wavelet analysis of CalderónZygmund and pseudodifferential operators, to numerically enforce the emergence of a natural hierarchical coarse graining of a manifold, graph or data set. For example for a body of text documents the construction leads to a directory structure at different levels of generalization. The dyadic powers of an operator can be used to induce a multiresolution analysis, as in classical LittlewoodPaley and wavelet theory: we construct, with efficient and stable algorithms, bases of orthonormal scaling functions and wavelets associated to this multiresolution analysis, together with the corresponding downsampling operators, and use them to compress the corresponding powers of the operator. While most of our discussion deals with symmetric operators and relates to localization to spectral bands, the symmetry of the operators and their spectral theory need not be considered, as the main assumption is reduction of the numerical ranks as we take powers of the operator. © 2006 Elsevier Inc. All rights reserved.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

