  We introduce a novel harmonic analysis for functions defined on the vertices
of a strongly connected directed graph 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
directed graphs. We found 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 directed
graphs. We propose both a redundant wavelet transform and a decimated wavelet
transform by extending the diffusion wavelets framework by Coifman and Maggioni
for directed graphs. The development of our harmonic analysis on directed
graphs thus leads us to consider both semi-supervised learning problems and
signal modeling problems on graphs applied to directed graphs highlighting the
efficiency of our framework.
