Fast Fourier transform for graph Laplacian? In the case of a regularly-sampled scalar-valued signal $f$ on the real line, we can construct a discrete linear operator $A$ such that $A(f)$ approximates $\partial^2 f / \partial x^2$.  One way to interpret this operator is via spectral decomposition of the corresponding matrix:
$$A = UVU^T.$$
If our operator $A$ has spectral accuracy, then $U^T$ is precisely the discrete Fourier transform matrix.  Hence, we could compute the Fourier transform of $x$ by computing all the eigenvectors of $A$ and sticking them in the columns of $U$.  Of course, we all know there's a quicker way to do it: use the fast Fourier transform (FFT).
What about in a more general setting?  In particular, consider the graph Laplacian $L=UVU^T$ which for a weighted, undirected graph on $n$ vertices is an $n \times n$ matrix with the weights of incident vertices on the off-diagonal and (the additive inverse of) total incident weight on the diagonal.
Question:
Can we transform a signal on vertices into frequency space without computing the entire spectrum of $L$ (using something like the FFT)?
In particular I'm interested in the case where $L$ approximates the Laplace-Beltrami operator on some manifold $M$ — here eigenvectors of $L$ approximate an orthogonal eigenbasis for square-integrable functions on $M$.  However, pointers to nearby results (e.g., FFT for the combinatorial graph Laplacian) are appreciated.
 A: The trick to making the FFT work is factoring out a complex exponential from the sum over odd terms. For this to happen your function needs to be sampled across a uniform grid. Greengard refers to this property as "brittle" (cf math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf ).
When your function is sampled over a nonuniform grid fast multipole methods or Barnes-Hut style algorithms can help.
A: I haven't looked at that area since my M.Sc. so take it with a grain of salt, but there was a conjecture, simultaneously extraordinary, under-appreciated, and probably intractable, that all Fourier transforms can be done in "quasi-linear time".
More realistically, a decade or two back, I remember what I thought was a breakthrough: preconditioners for solving diagonally-dominant systems in essentially linear time. Apparently, the rest of the math community didn't agree with me, because I can't find the precise paper, but the following reference is probably good enough:
Spielman, Teng, Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
Depending on your religion on eigenvalue algorithms, this could conceivably be turned into a "sort of linear time" eigenvalue algorithm.
