Institut de Mathématiques de Marseille, UMR 7373


Accueil >

Intertwinning wavelets or multiresolution analysis on graphs through random forests

Vendredi 17 novembre 13:30-14:30 - Clothilde MÉLOT - I2M, Marseille

Intertwinning wavelets or multiresolution analysis on graphs through random forests

Résumé : 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.

Lieu : CMI, salle de séminaire R164 (1er étage) - I2M - Château-Gombert
39 rue Frédéric Joliot-Curie
13453 Marseille cedex 13

Exporter cet événement

Pour en savoir plus sur cet événement, consultez l'article Séminaire Signal et Apprentissage