A Directed Graph Fourier Transform with Spread Frequency Components

Understand

We study the problem of constructing a graph Fourier transform (GFT) for directed graphs (digraphs), which decomposes graph signals into different modes of variation with respect to the underlying network.

• Accordingly, to capture low, medium and high frequencies we seek a digraph (D)GFT such that the orthonormal frequency components are as spread as possible in the graph spectral domain.
• To that end, we advocate a two-step design whereby we: (i) find the maximum directed variation (i.e., a novel notion of frequency on a digraph) a candidate basis vector can attain; and (ii) minimize a smooth spectral dispersion function over the achievable frequency range to obtain the desired spread DGFT basis.
• Both steps involve non-convex, orthonormality-constrained optimization problems, which are efficiently tackled via a provably convergent, feasible optimization method on the Stiefel manifold.