Intertwinning wavelets or multiresolution analysis on graphs through random forests
Date(s) : 17/11/2017 iCal
13h30 - 14h30
Several methods are available to analyze signals on graphs, i.e functions defined on the vertices of a finite connected weighted graph. Fourier analysis requires the computation of the eigenvalues and eigenvectors of the graph Laplacian, it is also a non-local transformation. In this talk we will propose a multiresolution scheme which provides well localized basis functions without requiring spectral computations.
Our approach relies on a random spanning forest to downsample the set of vertices, and on approximate solutions of Markov intertwining relation to provide a subgraph structure, and a filter bank , leading to a wavelet basis of the set of functions. Our construction involves two parameters q and q′. The first one controls the mean number of kept vertices in the downsampling, while the second one is a tuning parameter between space localization and frequency localization. Even if our basis functions are well localized, they are not orthonormal but we can provide an explicit reconstruction formula, bounds on the reconstruction operator norm, on the error in the intertwining relation, and a Jackson-like inequality. These bounds lead to recommend a way to choose the parameters q and q′. We illustrate the method by numerical experiments.
Catégories Pas de Catégories
