Analyzing the Approximation Error of the Fast Graph Fourier Transform
For researchers using graph Fourier transforms, this work provides insights into the trade-off between computational efficiency and approximation accuracy, but is incremental.
The paper analyzes the approximation error of a fast graph Fourier transform (FGFT) computed via truncated Jacobi rotations, studying how error distributes across the spectrum for different graphs.
The graph Fourier transform (GFT) is in general dense and requires O(n^2) time to compute and O(n^2) memory space to store. In this paper, we pursue our previous work on the approximate fast graph Fourier transform (FGFT). The FGFT is computed via a truncated Jacobi algorithm, and is defined as the product of J Givens rotations (very sparse orthogonal matrices). The truncation parameter, J, represents a trade-off between precision of the transform and time of computation (and storage space). We explore further this trade-off and study, on different types of graphs, how is the approximation error distributed along the spectrum.