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.


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.

  • 4
    $\begingroup$ 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." $\endgroup$ Apr 10 '10 at 3:22
  • $\begingroup$ This paper is available at, e.g. scholar.google.com/… $\endgroup$ Apr 10 '10 at 3:22
  • $\begingroup$ @SteveHuntsman It now says Your search did not match any articles. $\endgroup$
    – Ziyuan Lin
    May 22 '15 at 14:14

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.