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.

翻译：定向图形(digraphs) 上的信号处理有问题, 因为图形转换, 因而相关过滤器一般无法进行分解。 此外, 此情况下的 Fourier 变形目前来自约旦的分解, 可能无法对大图形进行计算。 我们根据矩阵扰动理论提出了解决这一问题的新颖和一般的解决方案: 我们设计了一个算法, 将少量的边缘添加到特定的分解中, 以摧毁非三重约旦区块。 获得的分解随后可以进行分解并产生, 正如我们所显示的那样, 原始的分解仪的大约为天体变形和 Fourier 变形。 我们解释为什么和如何可以将这一构造视为通用的边界条件形式, 这是信号处理的一种常见做法 。 我们用随机和真实的世界图形进行的实验显示, 我们可以以几千个节点的图表为尺度, 并获得接近于直观的四倍变形变形, 同时仍然对直观的感知概念进行分解。 我们的方法与相近和拉平梯变变变变变变换和微变换程序一起进行进一步的处理, 可以作为预处理程序。 。