  Signal processing on directed graphs (digraphs) is problematic, since the
graph shift, and thus associated filters, are in general not diagonalizable.
Furthermore, the Fourier transform in this case is now obtained from the Jordan
decomposition, which may not be computable at all for large graphs. We propose
a novel and general solution for this problem based on matrix perturbation
theory: We design an algorithm that adds a small number of edges to a given
digraph to destroy nontrivial Jordan blocks. The obtained digraph is then
diagonalizable and yields, as we show, an approximate eigenbasis and Fourier
transform for the original digraph. We explain why and how this construction
can be viewed as generalized form of boundary conditions, a common practice in
signal processing. Our experiments with random and real world graphs show that
we can scale to graphs with a few thousands nodes, and obtain Fourier
transforms that are close to orthogonal while still diagonalizing an intuitive
notion of convolution. Our method works with adjacency and Laplacian shift and
can be used as preprocessing step to enable further processing as we show with
a prototypical Wiener filter application.
