Wavelets on graphs via spectral graph theory (Q629253): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q284701 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: István Mezö / rank | |||
Normal rank |
Revision as of 09:26, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Wavelets on graphs via spectral graph theory |
scientific article |
Statements
Wavelets on graphs via spectral graph theory (English)
0 references
9 March 2011
0 references
The classical continuous wavelet transform can be generated by the choice of a single ``mother'' wavelet \(\psi\). Other wavelets (with different locations and spatial scales) are formed by transforming the mother wavelet, for example, \(\psi_{s,a}(x)=\frac1s\psi\left(\frac{x-a}{s}\right)\). Then for any suitable function (i.e. signal), the wavelet coefficients at scale \(s\) and location \(a\) can be given with \(\psi_{s,a}\). Conversely, the wavelet coefficients enable us to reconstruct the original signal. Several practical applications require discrete underlying spaces. The authors work out a possible framework of discrete wavelet transformation on weighted graphs. The first problem is the following: how to define \(\psi(sx)\) if \(x\) is a vertex of a graph? There is no expressive meaning of \(sx\), where \(s\) is a real scalar. The authors get around the problem as follows. They define the Laplacian \[ (\mathcal{L}f)(m)=\sum_{n\sim m}a_{m,n}(f(m)-f(n)), \] where \(a_{m,n}\) is the adjacency matrix of the weighted graph and \(f\) is a real valued function on the vertices. Since the usual one-dimensional Fourier transform uses the eigenfunctions of the Laplacian (i.e. the functions \(e^{i\omega x}\)), one may define the Fourier transform according to the eigenvectors of the Laplacian above. The authors go further and work out the spectral graph wavelet transform (SGWT) and deduces a number of its properties. It is also shown how can one speed up the SGWT-computations and apply it in practical applications, like transportation networks. An implemented algorithm can be found at \url{wiki.epfl.ch/sgwt}.
0 references
graph theory
0 references
spectral graph theory
0 references
wavelets
0 references
frames
0 references
overcomplete wavelet frames
0 references