A Sparse Data Structure for Graph Fourier Transforms

The plane wave transform (PWT) plays an important role in computational modeling of electromagnetic field interaction problems. It has recently been determined that the plane wave transform has an interpolation-free <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(N\log N)$</tex> representation. The same data structure is here shown to provide an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}(\mathrm{N}\log \mathrm{N})$</tex> representation of the discrete Fourier transform (DFT). It is well known that the DFT matrix is the eigen basis of the graph Laplacian associated with points on a line. This presentation explores the performance observed when the same data structure is used to compress the graph Fourier transform for more complex graphs.