  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. This specification gives rise to a challenging nonconvex
optimization problem, so we resort to a simple yet efficient heuristic to
construct the DGFT basis from Laplacian eigenvectors of an undirected version
of the digraph. To select frequency components which are as spread as possible,
we define a spectral dispersion function and show that it is supermodular.
Moreover, we show that orthonormality can be enforced via a matroid basis
constraint, which motivates adopting a scalable greedy algorithm to obtain an
approximate solution with provable performance guarantee. The effectiveness of
the novel DGFT is illustrated through numerical tests on synthetic and
real-world graphs.
