Diffusion wavelets
Diffusion wavelets are a fast multiscale framework for the analysis of functions on discrete (or discretized continuous) structures like graphs, manifolds, and point clouds in Euclidean space.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Diffusion wavelets are a fast multiscale framework for the analysis of functions on discrete (or discretized continuous) structures like graphs, manifolds, and point clouds in Euclidean space. Diffusion wavelets are an extension of classical wavelet theory from harmonic analysis. Unlike classical wavelets whose basis functions are predetermined, diffusion wavelets are adapted to the geometry of a given diffusion operator T (e.g., a heat kernel or a random walk). Moreover, the diffusion wavelet basis functions are constructed by dilation using the dyadic powers (powers of two) of T. These dyadic powers of T diffusion over the space and propagate local relationships in the function throughout the space until they become global. And if the rank of higher powers of T decrease (i.e., its spectrum decays), then these higher powers become compressible. From these decaying dyadic powers of T comes a chain of decreasing subspaces. These subspaces are the scaling function approximation subspaces, and the differences in the subspace chain are the wavelet subspaces.
Diffusion wavelets were first introduced in 2004 by Ronald Coifman and Mauro Maggioni at Yale University.[1]
Contents
Algorithm
edit edit sourceThis algorithm constructs the scaling basis functions and the wavelet basis functions along with the representations of the diffusion operator T at these scales.
In the algorithm below, the subscript notation Φa and Ψb represents the scaling basis functions at scale a and the wavelet basis functions at scale b respectively. The notation [Φb]Φa denotes the matrix representation of the scaling basis Φb represented with respect to the basis Φa. Lastly, the notation [T]ΦaΦb denotes the matrix represents of the operator T, where the row space of T is represented with respect to the basis Φa, and the column space of T is represented with respect to the basis Φb. Otherwise put, the domain of operator T is represented with respect to the basis Φa and the range is represented with respect to the basis Φb. The function QR is a sparse QR decomposition with ϵ precision.[2]
// Input: // T is the matrix representation of the diffusion operator. // ϵ is the precision of the QR decomposition, e.g., 1e-6. // J is the maximum number of scale levels (note: this is an optional upper bound, it may converge sooner.) // Output: // {Φj} is the set of scaling basis functions indexed by scale j. // {Ψj} is the set of wavelet basis functions indexed by scale j. {Φj},{Ψj}←function DiffusionWaveletTree(T,ϵ,J): 𝐟𝐨𝐫j←0 to J−1: [Φj+1]Φj,[T2j]ΦjΦj+1←QR([T2j]ΦjΦj,ϵ) [T2j+1]Φj+1Φj+1←([T2j]ΦjΦj+1[Φj+1]Φj)2 [Ψj]Φj←QR(I⟨Φj⟩−[Φj+1]Φj([Φj+1]Φj)∗,ϵ) 𝐞𝐧𝐝𝐟𝐨𝐫Applications
edit edit sourceMathematics
edit edit sourceDiffusion wavelets are of general interest in mathematics. Specifically, they allow for the direct calculation of the Green′s function and the inverse graph Laplacian.
Computer science
edit edit sourceDiffusion wavelets have been used extensively in computer science, especially in machine learning. They have been applied to the following fields:
- solving Markov decision processes and Markov chains for machine learning,[3]
- transfer learning,[4]
- value function approximation in reinforcement learning,[5]
- dimensionality reduction,[6]
- mesh compression for 3D graphics,[7]
- topic model analysis of document corpora.[8]
- relation extraction. [9]
See also
edit edit sourceReferences
edit edit source- ^ Coifman, Ronald; Mauro Maggioni (May 2008). "Diffusion Wavelets" (PDF). Applied and Computational Harmonic Analysis. 24 (3): 329–353. Archived from the original (PDF) on 2012-04-22.
- ^ Maggioni, Mauro; Mahadevan, Sridhar (2006). Fast Direct Policy Evaluation using Multiscale Analysis of Markov Diffusion Processes (PDF). The 23rd International Conference on Machine Learning.
- ^ Mahadevan, Sridhar (2008). "Learning Representation and Control in Markov Decision Processes". Foundations and Trends in Machine Learning. 1 (4).
- ^ Wang, Chang; Mahadevan, Sridhar (2010). "Multiscale Manifold Alignment" (PDF). Univ. Of Massachusetts Technical Report (UM-CS-2010-049).
- ^ Mahadevan, Sridhar; Maggioni, Mauro (2006). "Value Function Approximation using Diffusion Wavelets and Laplacian Eigenfunctions" (PDF). Advances in Neural Information Processing Systems.
- ^ Wang, Chang; Mahadevan, Sridhar (2009). "Multiscale Dimensionality Reduction with Diffusion Wavelets" (PDF). Univ. Of Massachusetts Technical Report (UM-CS-2009-030).
- ^ Mahadevan, Sridhar (2007). Adaptive Mesh Compression in 3D Computer Graphics using Multiresolution Manifold Learning (PDF). The 24th International Conference on Machine Learning.
- ^ Wang, Chang; Mahadevan, Sridhar (2009). "Multiscale Analysis of Document Corpora Based on Diffusion Models" (PDF). In Boutilier, Craig (ed.). IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009. pp. 1592–1597.
- ^ Wang, Chang; Fan, James; Kalyanpur, Aditya; Gondek, David (2011), "Relation Extraction with Relation Topics", Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, EMNLP 2011, 27–31 July 2011, John McIntyre Conference Centre, Edinburgh, UK, A meeting of SIGDAT, a Special Interest Group of the ACL, Association for Computational Linguistics, pp. 1426–1436
External links
edit edit source- Mauro Maggioni's MATLAB code implementation
- Chang Wang's diffusion wavelet page[link removed]
Text derived from https://en.wikipedia.org/w/index.php?oldid=1372674018 under CC BY-SA 4.0; modifications have been made.