论文标题
具有广义边界条件的Digraph信号处理
Digraph Signal Processing with Generalized Boundary Conditions
论文作者
论文摘要
在有向图上的信号处理（Digraphs）是有问题的，因为图形移位以及相关的过滤器通常不可对角线。此外，在这种情况下，傅立叶变换现在是从约旦分解中获得的，这对于大图可能根本不可计算。我们根据基质扰动理论提出了针对此问题的新颖和一般解决方案：我们设计了一种算法，该算法将少量边缘添加到给定的Digraph中以破坏非平凡的Jordan块。然后，所获得的挖掘物是可对角线的，正如我们所表明的那样，对于原始挖掘机而言，产量近似和傅立叶变换。我们解释了为什么以及如何将这种构建视为边界条件的广义形式，这是信号处理中的常见实践。我们使用随机和现实世界图的实验表明，我们可以扩展到数千个节点的图表，并获得接近正交的傅立叶变换，同时仍将直观的卷积概念对角化。我们的方法可与邻接和拉普拉斯偏移一起使用，可以用作预处理步骤，以在我们使用典型的Wiener滤波器应用程序显示时进行进一步的处理。
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.
