# Diffusion wavelets

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Diffusion_wavelets
> Markdown URL: https://mediated.wiki/source/Diffusion_wavelets.md
> Source: https://en.wikipedia.org/wiki/Diffusion_wavelets
> Source revision: 1348933817
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

**Diffusion wavelets** are a fast multiscale framework for the analysis of functions on discrete (or discretized continuous) structures like [graphs](/source/Graph_(discrete_mathematics)), [manifolds](/source/Manifold_(mathematics)), and [point clouds](/source/Point_cloud) in [Euclidean space](/source/Euclidean_space). Diffusion wavelets are an extension of classical [wavelet theory](/source/Wavelet) from [harmonic analysis](/source/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](/source/Heat_kernel) or a [random walk](/source/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](/source/Wavelet#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](/source/Ronald_Coifman) and Mauro Maggioni at Yale University.[1]

## Algorithm

This 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 \Phi_a and \Psi_b represents the scaling basis functions at scale a and the wavelet basis functions at scale b respectively. The notation [\Phi_b]_{\Phi_a} denotes the matrix representation of the scaling basis \Phi_b represented with respect to the basis \Phi_a. Lastly, the notation [T]_{\Phi_a}^{\Phi_b} denotes the matrix represents of the operator T, where the [row space](/source/Row_space) of T is represented with respect to the basis \Phi_a, and the [column space](/source/Column_space) of T is represented with respect to the basis \Phi_b. Otherwise put, the domain of operator T is represented with respect to the basis \Phi_a and the range is represented with respect to the basis \Phi_b. The function QR is a sparse [QR decomposition](/source/QR_decomposition) with \epsilon precision.[2]

// Input: // T is the matrix representation of the diffusion operator. // \epsilon 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: // \lbrace\Phi_j\rbrace is the set of scaling basis functions indexed by scale j. // \lbrace\Psi_j\rbrace is the set of wavelet basis functions indexed by scale j.

\lbrace\Phi_j\rbrace, \lbrace\Psi_j\rbrace \leftarrow \text{function DiffusionWaveletTree} ( T , \epsilon , J ): \textbf{for } j\leftarrow 0 \text{ to } J-1: [\Phi_{j+1}]_{\Phi_j}, [T^{2^j}]_{\Phi_j}^{\Phi_{j+1}} \leftarrow QR\left([T^{2^j}]_{\Phi_j}^{\Phi_{j}}, \epsilon\right) [T^{2^{j+1}}]_{\Phi_{j+1}}^{\Phi_{j+1}} \leftarrow \left([T^{2^j}]_{\Phi_j}^{\Phi_{j+1}} [\Phi_{j+1}]_{\Phi_j}\right)^2 [\Psi_j]_{\Phi_j} \leftarrow QR\left(I_{\langle\Phi_j\rangle}-[\Phi_{j+1}]_{\Phi_j}\left([\Phi_{j+1}]_{\Phi_j}\right)^*, \epsilon\right) \textbf{end for}

## Applications

### Mathematics

Diffusion wavelets are of general interest in mathematics. Specifically, they allow for the direct calculation of the [Green′s function](/source/Green%E2%80%B2s_function) and the inverse [graph Laplacian](/source/Laplacian_matrix).

### Computer science

Diffusion wavelets have been used extensively in computer science, especially in [machine learning](/source/Machine_learning). They have been applied to the following fields:

- solving [Markov decision processes](/source/Markov_decision_process) and [Markov chains](/source/Markov_chains) for machine learning,[3]
- [transfer learning](/source/Transfer_learning),[4]
- value [function approximation](/source/Function_approximation) in [reinforcement learning](/source/Reinforcement_learning),[5]
- [dimensionality reduction](/source/Dimensionality_reduction),[6]
- mesh compression for 3D graphics,[7]
- [topic model](/source/Topic_model) analysis of document corpora.[8]
- relation extraction. [9]

## See also

- [Wavelets](/source/Wavelets)

## References

1. Coifman, Ronald & Mauro Maggioni (May 2008). ["Diffusion Wavelets"](https://web.archive.org/web/20120422151024/http://www.math.duke.edu/~mauro/Papers/DiffusionWavelets.pdf). *Applied and Computational Harmonic Analysis*. **24** (3): 329–353. Archived from [the original](http://www.math.duke.edu/~mauro/Papers/DiffusionWavelets.pdf) on 2012-04-22.

1. Maggioni, Mauro & Mahadevan, Sridhar (2006). [*Fast Direct Policy Evaluation using Multiscale Analysis of Markov Diffusion Processes*](https://www.cs.umass.edu/~mahadeva/papers/icml2006.pdf). The 23rd International Conference on Machine Learning.

1. Mahadevan, Sridhar (2008). "Learning Representation and Control in Markov Decision Processes". *Foundations and Trends in Machine Learning*. **1** (4)

1. Wang, Chang & Mahadevan, Sridhar (2010). ["Multiscale Manifold Alignment"](https://www.cs.umass.edu/~mahadeva/papers/UM-CS-2010-049.pdf). *Univ. Of Massachusetts Technical Report*. '***(UM-CS-2010-049)***

1. Mahadevan, Sridhar & Maggioni, Mauro (2006). ["Value Function Approximation using Diffusion Wavelets and Laplacian Eigenfunctions"](https://www.cs.umass.edu/~mahadeva/papers/nips-paper1-v5.pdf). *Advances in Neural Information Processing Systems*

1. Wang, Chang & Mahadevan, Sridhar (2009). ["Multiscale Dimensionality Reduction with Diffusion Wavelets"](https://www.cs.umass.edu/~mahadeva/papers/TR-2009-DP.pdf). *Univ. Of Massachusetts Technical Report*. '***(UM-CS-2009-030)***

1. Mahadevan, Sridhar (2007). [*Adaptive Mesh Compression in 3D Computer Graphics using Multiresolution Manifold Learning*](https://www.cs.umass.edu/~mahadeva/papers/sridhar-icml07.pdf). The 24th International Conference on Machine Learning.

1. Wang, Chang & Mahadevan, Sridhar (2009). ["Multiscale Analysis of Document Corpora Based on Diffusion Models"](https://ijcai.org/Proceedings/09/Papers/266.pdf). *IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009*. Boutilier, Craig (ed.). pp. 1592–1597.

1. Wang, Chang; Fan, James; Kalyanpur, Aditya; Gondek, David (2011), ["Relation Extraction with Relation Topics"](https://aclanthology.org/D11-1132/), "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

- [Mauro Maggioni's MATLAB code implementation](https://web.archive.org/web/20120308014909/http://www.math.duke.edu/~mauro/code.html)
- [Chang Wang's diffusion wavelet page](https://archive.today/20121212094349/http://www.cs.umass.edu/~chwang/dwt.html)

---
Adapted from the Wikipedia article [Diffusion wavelets](https://en.wikipedia.org/wiki/Diffusion_wavelets) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Diffusion_wavelets?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.