Circulant Matrices and the Fast Fourier Transform for Efficient Neural Networks

This direction is merged into another direction: frequency-domain convolution. Its last version stays readable and citable here.

Version 1 of 133 papers41 conceptsfrozen 2026-10-04

In modern deep learning, the standard fully-connected layer is a computational bottleneck. A weight matrix $W \in \mathbb{R}^{d \times d}$ requires $O(d^2)$ parameters to store and $O(d^2)$ operations to compute. As models scale, this quadratic growth becomes unsustainable.

A powerful alternative has emerged: replacing dense matrices with circulant matrices. By leveraging the mathematical relationship between circulant structures and the frequency domain, researchers can reduce memory requirements to $O(d)$ and computational complexity to $O(d \log d)$. This shift allows for high-rank, expressive transformations at a fraction of the cost of traditional layers.

The Geometry of Circulant Projections

A circulant matrix is a square matrix where each row is a cyclic shift of the row above it. This means the entire matrix is defined by a single vector $c = [c_0, c_1, \dots, c_{d-1}]$.

$$ W = \begin{bmatrix} c_0 & c_{d-1} & \dots & c_1 \\ c_1 & c_0 & \dots & c_2 \\ \vdots & \vdots & \ddots & \vdots \\ c_{d-1} & c_{d-2} & \dots & c_0 \end{bmatrix} $$

Felix X. Yu, Sanjiv Kumar, and colleagues demonstrated in An exploration of parameter redundancy in deep networks with circulant projections that these structures can replace standard layers with minimal loss in accuracy. The intuition is that deep networks are often massively over-parameterized; the structured "mixing" provided by a circulant matrix is often sufficient to capture the necessary features.

The FFT as a Computational Shortcut

The reason circulant matrices are so efficient is the Circular Convolution Theorem. Multiplying a vector $x$ by a circulant matrix $W$ is mathematically equivalent to the circular convolution of the defining vector $c$ and the input $x$.

In the spatial domain, convolution is expensive. However, in the frequency domain, convolution becomes simple element-wise multiplication. By using the Fast Fourier Transform (FFT), we can compute the product $Wx$ as:

$$Wx = \mathcal{F}^{-1}(\mathcal{F}(c) \odot \mathcal{F}(x))$$

where $\mathcal{F}$ is the FFT and $\odot$ is the Hadamard (element-wise) product. This reduces the complexity from $O(d^2)$ to $O(d \log d)$. Zhe Li and Caiwen Ding have shown that this transformation is particularly effective for hardware acceleration on FPGAs, where it enables significant energy efficiency and speedups for Recurrent Neural Networks (Efficient Recurrent Neural Networks using Structured Matrices in FPGAs).

Beyond Low-Rank: The Expressivity Advantage

A common way to reduce parameters is Low-Rank Adaptation (LoRA), which approximates a weight update as $BA$, where $B$ and $A$ are thin matrices. However, low-rank methods are inherently limited in their expressivity—they can only represent updates in a restricted subspace.

Circulant matrices offer a "best of both worlds" scenario. As Arijit Sehanobish and Krzysztof Marcin Choromanski argue in Structured Unrestricted-Rank Matrices for Parameter Efficient Finetuning, circulant and Toeplitz matrices can be full-rank while still being defined by only $O(d)$ parameters.

This "unrestricted rank" property is the core of Circular Convolution Adaptation (C3A). Aochuan Chen and Jia Li found that C3A can outperform LoRA in fine-tuning tasks because it doesn't suffer from the "rank bottleneck," allowing the model to learn more complex adaptations with even fewer parameters (Parameter-Efficient Fine-Tuning via Circular Convolution).

Modern Refinements and Hardware Realities

While the theoretical benefits of FFT-based layers are clear, practical implementation requires addressing memory and hardware overhead.

  1. 1D vs 2D Transforms: Recent work like CDVFT by Xinyu Ding and Zhongfeng Wang suggests that using 1D FFTs to handle circulant and diagonal vectors is more efficient than 2D frequency domain reconstructions, reducing FLOPs by up to 51x compared to earlier Fourier-based methods (Parameter-Efficient Fine-Tuning with Circulant and Diagonal Vectors).
  2. In-Place Operations: Standard FFT libraries often require extra memory buffers. Xinyu Ding introduced rdFFT, a real-domain, in-place FFT that packs complex conjugate pairs into the original input tensor, eliminating intermediate memory allocation during training (Memory-Efficient Training with In-Place FFT Implementation).
  3. Hardware Specialization: While FFTs are algorithmically superior, hardware like Google's TPU is optimized for dense matrix multiplication. Yi-Fan Chen showed that for very large scales, it is sometimes more efficient to reformulate the DFT itself as a series of dense matrix multiplications to exploit specialized hardware units (Large-Scale Discrete Fourier Transform on TPUs).

Applications Across Domains

The utility of circulant structures extends beyond simple compression:

By treating neural network weights as signals in the frequency domain, this research direction provides a mathematically grounded path toward models that are both smaller and more expressive.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_circulant_matrices_and_the_fast_fourier__ba8b282a,
  title = {Circulant Matrices and the Fast Fourier Transform for Efficient Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/circulant-matrices-and-the-fast-fourier-transform-for-efficient-neural-networks/rdr_ba8b282a67b64145ad70b53696aca208},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_circulant_matrices_and_the_fast_fourier__ba8b282a_v1,
  title = {Circulant Matrices and the Fast Fourier Transform for Efficient Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/circulant-matrices-and-the-fast-fourier-transform-for-efficient-neural-networks/rdr_ba8b282a67b64145ad70b53696aca208/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}