Graph Fourier Transform: A Stable Approximation
Graph Fourier Transform: A Stable Approximation
复制标题
DOI：
10.1109/tsp.2020.3009645
复制
发表时间：
2020-01
影响因子：
5.4
通讯作者：
João Domingos;J. Moura
中科院分区：
文献类型：
--
作者：
João Domingos;J. Moura
在图形信号处理（GSP）中，数据依赖性由图形表示，图形的节点标记数据，边缘捕获节点之间的依赖性。该图由加权邻接矩阵$A$表示，在GSP中，该矩阵推广了离散信号处理（DSP）移位运算符$z^{-1}$。移位$A$（图形频谱分量）的（右）特征向量对角化$A$并且导致提供图形信号的图形频谱表示的图形傅立叶基$F$。图傅立叶基的（矩阵）的逆是图傅立叶变换（GFT），F^{-1}$。通常，包括在真实的世界的例子中，这种对角化在数值上是不稳定的。本文通过求解一个非凸优化问题，给出了一种精确逼近F和F^{-1}的方法，同时保证了它们的数值稳定性。为了解决非凸性，我们提出了一种算法，稳定的图形傅立叶基算法（SGFA），以指数方式提高近似F$每次迭代的准确性。同样地，我们可以将SGFA应用于$A^H$，因此近似图移位$A$的稳定左特征向量并直接计算GFT。我们评估经验的质量SGFA应用它的图形变化$A$从两个真实的世界的问题，2004年美国的政治博客图和曼哈顿路线图，进行了全面的研究，不同的SGFA参数之间的权衡。我们还证实了我们的结论，应用SGFA非常稀疏和非常密集的有向Erdens-Rényi图。
In graph signal processing (GSP), data dependencies are represented by a graph whose nodes label the data and the edges capture dependencies among nodes. The graph is represented by a weighted adjacency matrix $A$ that, in GSP, generalizes the Discrete Signal Processing (DSP) shift operator $z^{-1}$. The (right) eigenvectors of the shift $A$ (graph spectral components) diagonalize $A$ and lead to a graph Fourier basis $F$ that provides a graph spectral representation of the graph signal. The inverse of the (matrix of the) graph Fourier basis $F$ is the Graph Fourier transform (GFT), $F^{-1}$. Often, including in real world examples, this diagonalization is numerically unstable. This paper develops an approach to compute an accurate approximation to $F$ and $F^{-1}$, while insuring their numerical stability, by means of solving a non convex optimization problem. To address the non-convexity, we propose an algorithm, the stable graph Fourier basis algorithm (SGFA) that improves exponentially the accuracy of the approximating $F$ per iteration. Likewise, we can apply SGFA to $A^H$ and, hence, approximate the stable left eigenvectors for the graph shift $A$ and directly compute the GFT. We evaluate empirically the quality of SGFA by applying it to graph shifts $A$ drawn from two real world problems, the 2004 US political blogs graph and the Manhattan road map, carrying out a comprehensive study on tradeoffs between different SGFA parameters. We also confirm our conclusions by applying SGFA on very sparse and very dense directed Erdős-Rényi graphs.