Fourier transform of a function on a graph

What is a Fourier transform at its core? An expansion of function in terms of eigenfunctions of the Laplacian. For a function on the real line, the Laplacian is simply the second derivative. The functions mapped to multiples of themselves by taking second derivatives are sines and cosines of various frequencies. A Fourier series is a change of basis, using as basis vectors those functions who behave the simplest under the second derivative.

The Fourier transform of a function on a graph is also a change of basis, expanding a discrete function in terms of eigenvalues of the Laplacian, in this case the graph Laplacian.

The Fourier transform of a function f, evaluated at a frequency ω, is the inner product of f with the eigenfunction exp(2πiωt).

\hat{f}(\omega) = \langle f, \exp(2\pi i \omega t) \rangle = \int_{-\infty}^\infty f(t) \exp(-2\pi i \omega t) \, dx

The inner product of two complex functions f and g is the integral of the product of f and the conjugate of g. Conjugation is why exp(2πiωt) became exp(-2πiωt).

The Fourier transform of a discrete function f on a graph, evaluated at an eigenvalue λi, is the inner product of f (i.e. the vector of values of f at each node) with the eigenvector associated with λi.

\hat{f}(\lambda_i) = \langle f, v^*_i \rangle = \sum_{j=1}^N f(j) v_i^*(j)

Here the inner product is a discrete sum rather than an integral. As before, we take the complex conjugate of the second item in the product.

The eigenvectors associated with the smallest eigenvalues of the graph Laplacian are analogous to low frequency sines and cosines. The eigenvalue components corresponding to nearly vertices in a graph should be close together. This analogy explains why spectral coordinates work so well.

Click to learn more about consulting for complex networks

 

Related:

6 thoughts on “Fourier transform of a function on a graph

  1. Thanks for the great post, John.

    Is v_i^*(j) the j-th element of the i-th eigenvector of the graph Laplacian?

    If that is the case, then a followup question is: under what conditions will v_i^*(j) be a complex number?

    The reason I ask the followup question is because I’ve never encountered an eigenvector of the Laplacian that is complex. But I believe it is possible to have complex eigenvectors be minimizers of

    $\lambda_k = min_{x \in \mathbb{R}^n, x \perp x_{k-1}} \frac{x^T L x}{x^Tx}$

    So I was wondering how the complex eigenvectors show up.

    Thanks,
    Sam

  2. v_i^*(j) the complex conjugate of the j-th element of the i-th eigenvector of the graph Laplacian.

    The graph Laplacian has only real entries and is symmetric (assuming the graph is undirected) and so the eigenvalues and eigenvectors will always be real.

  3. Correction. It should be
    $\lambda_k = min_{x \in \mathbb{C}^n, x \perp x_{k-1}} \frac{x^T L x}{x^Tx}$.
    Instead of
    $\lambda_k = min_{x \in \mathbb{R}^n, x \perp x_{k-1}} \frac{x^T L x}{x^Tx}$.

    Sam

  4. My confusion is really about how v_i can have any complex entries. As you said, the eigenvectors of the Laplacian are real.

    Sorry about my persistent ignorance. I am new to the topic.

Leave a Reply

Your email address will not be published. Required fields are marked *