Title: Analyzing the Approximation Error of the Fast Graph Fourier Transform,
Abstract: 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.