Answers are grounded in this paper and cite their sources.
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 matrixAthat, in GSP, generalizes the Discrete Signal Processing (DSP) shift operatorz⁻¹. The (right) eigenvectors of the shiftA(graph spectral components) diagonalizeAand lead to a graph Fourier basisFthat provides a graph spectral representation of the graph signal. The inverse of the (matrix of the) graph Fourier basisFis the Graph Fourier transform (GFT),F⁻¹. Often, including in real world examples, this diagonalization is numerically unstable. This paper develops an approach to compute an accurate approximation toFandF⁻¹, 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 approximatingFper iteration. Likewise, we can apply SGFA toAHand, hence, approximate the stable left eigenvectors for the graph shiftAand directly compute the GFT. We evaluate empirically the quality of SGFA by applying it to graph shiftsAdrawn 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.
No takes yet. Share an insight, caveat, or question.
Domingos et al. (2020) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: