Digraph Fourier Transform via Spectral Dispersion Minimization

Abstract

We address the problem of constructing a graph Fourier transform (GFT) for both undirected and directed graphs (digraphs), which decomposes graph signals into different modes of variation with respect to the underlying network. Accordingly, we seek orthonormal bases that yield maximally-spread frequency components in the graph spectral domain to better capture low, medium and high frequencies. To that end, we advocate a two-step design whereby we: (i) find the maximum directed variation (i.e., 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 GFT 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. We illustrate the effectiveness of the novel GFT construction algorithm through numerical tests on synthetic and real-world graphs.