# Discovering Transforms: A Tutorial on Circulant Matrices, Circular Convolution, and the Discrete Fourier Transform

arXiv: https://arxiv.org/abs/1805.05533 · HTML: https://mlsanity.com/paper/1805.05533/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2018.

## Built on by (most cited first, 8 of 8)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Towards Multi-spatiotemporal-scale Generalized PDE Modeling](https://mlsanity.com/paper/2209.15616/) (2022)
- [DISCO: accurate Discrete Scale Convolutions](https://mlsanity.com/paper/2106.02733/) (2021)
- [Functional Regularization for Reinforcement Learning via Learned Fourier Features](https://mlsanity.com/paper/2112.03257/) (2021)
- [Parameter-Efficient Fine-Tuning via Circular Convolution](https://mlsanity.com/paper/2407.19342/) (2024)
- [FastRPB: a Scalable Relative Positional Encoding for Long Sequence Tasks](https://mlsanity.com/paper/2202.11364/) (2022)
- [FUSE-ing Language Models: Zero-Shot Adapter Discovery for Prompt Optimization Across Tokenizers](https://mlsanity.com/paper/2408.04816/) (2024)
- [Pixel-Translation-Equivariant Quantum Convolutional Neural Networks via Fourier Multiplexers](https://mlsanity.com/paper/2604.06094/) (2026)

## Abstract (arXiv)

How could the Fourier and other transforms be naturally discovered if one didn't know how to postulate them? In the case of the Discrete Fourier Transform (DFT), we show how it arises naturally out of analysis of circulant matrices. In particular, the DFT can be derived as the change of basis that simultaneously diagonalizes all circulant matrices. In this way, the DFT arises naturally from a linear algebra question about a set of matrices. Rather than thinking of the DFT as a signal transform, it is more natural to think of it as a single change of basis that renders an entire set of mutually-commuting matrices into simple, diagonal forms. The DFT can then be "discovered" by solving the eigenvalue/eigenvector problem for a special element in that set. A brief outline is given of how this line of thinking can be generalized to families of linear operators, leading to the discovery of the other common Fourier-type transforms, as well as its connections with group representations theory.