Wavelets on graphs via spectral graph theory (Q629253)

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}.