Multiresolution analysis of functions on directed networks

Harry Sevi (1, 2, 3) , Gabriel Rilling (1, 2) , Pierre Borgnat (3)

1 LADIS (CEA, LIST) - Laboratoire d'analyse des données et d'intelligence des systèmes (CEA, LIST)
2 LIST (CEA) - Laboratoire d'Intégration des Systèmes et des Technologies
3 Phys-ENS - Laboratoire de Physique de l'ENS Lyon

We introduce a novel design for analyzing and approximating functions defined on the vertices of a directed graph Γ in a multi-scale fashion. The starting point of our construction is the setting-up of a frequency notion through the study of the Dirichlet energy of random walk operator's eigenfunctions. By this alluring frequency interpretation, the set of random walk's eigenfunctions is considered as the Fourier basis for functions over directed graphs. We are thus able to construct a multi-scale frame based on the bi-orthogonal basis of the random walk on directed graphs. This multi-resolution frame paves thus the way to a generalization of the diffusion wavelet framework to the directed scope.

Mots clés: Fourier basis; Frame-based; Novel design; Orthogonal basis; Random Walk; Directed graphs; Directed network; Dirichlet energy; Random processes; Multiresolution analysis; Eigenvalues and eigenfunctions; Signal processing

Domaines: Traitement du signal et de l'image [eess.SP]; Analyse numérique [math.NA]; Analyse de données, Statistiques et Probabilités [physics.data-an]

Harry Sevi, Gabriel Rilling, Pierre Borgnat. Multiresolution analysis of functions on directed networks. Wavelets and Sparsity XVII, Aug 2017, San diego, United States. pp.103941Q, ⟨10.1117/12.2274341⟩. ⟨cea-01809220⟩