# 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.

• From "Discrete Combinatorial Laplacian Operators for Digital Geometry Processing" by Hao Zhang: "the eigenvectors of the TL [Tutte Laplacian] represent the natural vibration modes of the mesh, while the corresponding eigenvalues capture its natural frequencies, resembling the scenario for [the] classical discrete Fourier Transform (DFT). However, the eigenvectors of the TL possess no analytical form in general and there are no fast methods, analogous to the Fast Fourier Transform, to compute the corresponding mesh signal transform." – Steve Huntsman Apr 10 '10 at 3:22
• This paper is available at, e.g. scholar.google.com/… – Steve Huntsman Apr 10 '10 at 3:22
• @SteveHuntsman It now says Your search did not match any articles. – Ziyuan Lin May 22 '15 at 14:14