Graph Fourier Transform: A Stable Approximation

Abstract

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 we prove to exponentially increase 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\H os-Rényi graphs.

arXiv comment16 pages, 17 figures. Originally submitted in -IEEE Transactions on Signal Processing- on 01-Aug-2019. Resubmitted on 12-Jan-2020. Accept with mandatory minor revisions. Resubmitted again on 30-April-2020

References in corpus (17)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Discrete Signal Processing on Graphs: Sampling Theory
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Signals on Graphs: Uncertainty Principle and Sampling
• Signal Recovery on Graphs: Variation Minimization
• Sampling of graph signals with successive local aggregations
• Stationary signal processing on graphs
• Stationary Graph Processes and Spectral Estimation
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• Angles in Complex Vector Spaces
• On the Graph Fourier Transform for Directed Graphs
• Spectral Domain Sampling of Graph Signals
• Spectral Projector-Based Graph Fourier Transforms
• SILVar: Single Index Latent Variable Models
• Graph Signal Processing: Modulation, Convolution, and Sampling
• Sensitivity and computation of a defective eigenvalue

Cited by in corpus (7)

• Causal Fourier Analysis on Directed Acyclic Graphs and Posets
• Digraph Signal Processing with Generalized Boundary Conditions
• The Generalized Fourier Transform: A Unified Framework for the Fourier, Laplace, Mellin and $Z$ Transforms
• Joint Time-Vertex Fractional Fourier Transform
• Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes
• Subset Random Sampling and Reconstruction of Finite Time-Vertex Graph Signals
• Multi-dimensional graph fractional Fourier transform and its application