Harmonic analysis on directed graphs and applications: From Fourier analysis to wavelets

We introduce a novel harmonic analysis for functions defined on the vertices of a strongly connected directed graph (digraph) of which the random walk operator is the cornerstone. As a first step, we consider the set of eigenvectors of the random walk operator as a non-orthogonal Fourier-type basis...

Full description

Saved in:
Bibliographic Details
Published in:Applied and computational harmonic analysis 2023, Vol.62, p.390-440
Main Authors: Sevi, Harry, Rilling, Gabriel, Borgnat, Pierre
Format: Article
Language:English
Subjects:
Computer Science
Mathematics
Numerical Analysis
Signal and Image Processing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce a novel harmonic analysis for functions defined on the vertices of a strongly connected directed graph (digraph) of which the random walk operator is the cornerstone. As a first step, we consider the set of eigenvectors of the random walk operator as a non-orthogonal Fourier-type basis for functions over digraphs. We find a frequency interpretation by linking the variation of the eigenvectors of the random walk operator obtained from their Dirichlet energy to the real part of their associated eigenvalues. From this Fourier basis, we can proceed further and build multi-scale analyses on digraphs. We propose both a redundant wavelet transform and a decimated wavelet transform as an extension of spectral graph wavelets and diffusion wavelets framework respectively for digraphs. The development of our harmonic analysis on digraphs thus leads us to consider both semi-supervised learning problems and signal modeling problems on graphs applied to digraphs highlighting the efficiency of our framework.
ISSN:1063-5203
1096-603X
DOI:10.1016/j.acha.2022.10.003