# Graph Fourier Transform: A Stable Approximation

arXiv: https://arxiv.org/abs/2001.05042 · HTML: https://mlsanity.com/paper/2001.05042/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2020.

## Built on by (most cited first, 5 of 5)

- [Causal Fourier Analysis on Directed Acyclic Graphs and Posets](https://mlsanity.com/paper/2209.07970/) (2022)
- [Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes](https://mlsanity.com/paper/2311.07596/) (2023)
- [A Novel Unified Extended Matrix for Graph Signal Processing: Theory and Application](https://mlsanity.com/paper/2508.16633/) (2025)
- [Rotation-Parameterized Graph Fractional Fourier Transform: Definition, Properties, and Optimal Filtering](https://mlsanity.com/paper/2511.16111/) (2025)
- [GFT-GCN: Privacy-Preserving 3D Face Mesh Recognition with Spectral Diffusion](https://mlsanity.com/paper/2511.19958/) (2025)

## Abstract (arXiv)

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 AH 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 ErdH os-R'enyi graphs.