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.
Best Answer
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.