  The Fast Fourier Transform (FFT) is an algorithm of paramount importance in
signal processing as it allows to apply the Fourier transform in O(n log n)
instead of O(n 2) arithmetic operations. Graph Signal Processing (GSP) is a
recent research domain that generalizes classical signal processing tools, such
as the Fourier transform, to situations where the signal domain is given by any
arbitrary graph instead of a regular grid. Today, there is no method to rapidly
apply graph Fourier transforms. We propose in this paper a method to obtain
approximate graph Fourier transforms that can be applied rapidly and stored
efficiently. It is based on a greedy approximate diagonalization of the graph
Laplacian matrix, carried out using a modified version of the famous Jacobi
eigenvalues algorithm. The method is described and analyzed in detail, and then
applied to both synthetic and real graphs, showing its potential.
