Intertwinning wavelets or multiresolution analysis on graphs through random forests

Carte non disponible

Date(s) - 17/11/2017
13 h 30 min - 14 h 30 min

Catégories Pas de Catégories

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.


Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange