Are There Approximate Fast Fourier Transforms On Graphs?

International audienceSignal processing on graphs is a recent research domain that seeks to extend classical signal processing tools such as the Fourier transform to irregular domains given by a graph. In such a graph setting, a way to rapidly apply the Fourier transform, i.e. a Fast Fourier Transform (FFT), is lacking. In this paper, we propose to leverage the recently introduced Flexible Approximate MUlti-layer Sparse Transforms (FAµST) in order to compute approximate FFTs on graphs. The approach is first described, then validated on several types of classical graphs and finally used for fast filtering, showing good potential