22
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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$
    – Steve Huntsman
    Commented Apr 10, 2010 at 3:22
  • $\begingroup$ This paper is available at, e.g. scholar.google.com/… $\endgroup$
    – Steve Huntsman
    Commented Apr 10, 2010 at 3:22
  • $\begingroup$ @SteveHuntsman It now says Your search did not match any articles. $\endgroup$
    – Ziyuan
    Commented May 22, 2015 at 14:14

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .