Circulant Matrices, Eigenvectors, and the FFT | Hacker News Reader

Circulant Matrices, Eigenvectors, and the FFT

johndcook.com

134 pointstodsacerdoti6 comments

The article shows the connection but it doesn't present an intuition of the why, which I think is by far more interesting, and it's key to understanding Fourier analysis.

You can take a vector and shift all its elements to the right by 1 (rotating the last entry to the first position), let's call this operator S. Since the rows of a circulant matrix C are all rotations, if you apply the shift S, then multiply by C, and then shift back, you get the same result as if you just multiplied by C. In equations, S^-1 C S = C.

This is another way of saying that circulant matrices are shift-invariant. If you have a vector of zeros and just a few values in the middle, the matrix doesn't care where those non-zeros are, the result is the same but shifted accordingly; intuitively, the matrix operates in the frequency domain, not in the spatial domain. This is the same idea behind convolutional neural networks: translation-invariance means that we can ignore the position of an object in an image, and thus share the parameters across all positions, reducing the parameter complexity from quadratic to linear.

Now one of the first things you learn in linear algebra is that if two matrixes commute, they share the eigenspaces. We know that SC = CS from the equation above, so if we want to find the eigenvectors of any C, we can just find the eigenvectors of S.

But if we write S in matrix form, it is just ones under the diagonal, and a one on the top right. That's the companion matrix [1] of x^n - 1! So the eigenvalues are the nth roots of unity, and that shows the connection.

These intuitions translate (haha) quite naturally to function spaces, where shift-invariant operators are diagonalized by Fourier series (for periodic functions) and Fourier transform (for non-periodic functions with finite energy).

[1] https://en.wikipedia.org/wiki/Companion_matrix

EDIT: I just remembered we don't even need to inconvenience the companion matrix. If ω is a n-th root of unit, and you have a vector which is [1, ω, ..., ω^{n-1}] and you multiply it by ω, you get [ω, ..., ω^{n-1}, 1] (because ωω^{n-1} = 1), which is exactly the original vector shifted by 1, so it is an eigenvector of S.

Nice explainer! I wonder, so do these FFT matrices have to satisfy some (dimensional) condition to ensure that an analogue of "3D gimbal lock" does not occur?

Thanks for taking the time to write that out, it was very engaging to read.

It is worth noting that circulant matrices are 1-dimensional convolutions with circular padding, and their properties can be extended to doubly-block circulant matrices, which are the 2-dimensional equivalent. The eigendecomposition of doubly-block circulant matrices has been exploited in the context of robustness and stability in deep learning [1, 2, 3].

[1] The Singular Values of Convolutional Layers

[2] Orthogonalizing Convolutional Layers with the Cayley Transform

[3] Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration

This is great, I've always known that (complex) exponentials are eigenfunction of translation, but never made the connection that this means an operator with translation-invariance property means that it cares only about frequency content.

Minor typo: "Here’s a surprising property of circulant matrices: the eigenvectors of a circulatnt [sic] matrix depend only on the size of the matrix, not on the elements of the matrix."

Reply on news.ycombinator.com