# Very Efficient Training of Convolutional Neural Networks using Fast Fourier Transform and Overlap-and-Add

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2016.

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

- [FNet: Mixing Tokens with Fourier Transforms](https://mlsanity.com/paper/2105.03824/) (2021)
- [Active Learning for Deep Object Detection via Probabilistic Modeling](https://mlsanity.com/paper/2103.16130/) (2021)
- [Resource-Efficient Deep Learning: A Survey on Model-, Arithmetic-, and Implementation-Level Techniques](https://mlsanity.com/paper/2112.15131/) (2021)
- [Fast-FNet: Accelerating Transformer Encoder Models via Efficient Fourier Layers](https://mlsanity.com/paper/2209.12816/) (2022)
- [FourierNet: Shape-Preserving Network for Henle's Fiber Layer Segmentation in Optical Coherence Tomography Images](https://mlsanity.com/paper/2201.06435/) (2022)
- [Faster Convolution Inference Through Using Pre-Calculated Lookup Tables](https://mlsanity.com/paper/2104.01681/) (2021)
- [Phasor-Driven Acceleration for FFT-based CNNs](https://mlsanity.com/paper/2406.00290/) (2024)

## Abstract (arXiv)

Convolutional neural networks (CNNs) are currently state-of-the-art for various classification tasks, but are computationally expensive. Propagating through the convolutional layers is very slow, as each kernel in each layer must sequentially calculate many dot products for a single forward and backward propagation which equates to O(N2n2) per kernel per layer where the inputs are N × N arrays and the kernels are n × n arrays. Convolution can be efficiently performed as a Hadamard product in the frequency domain. The bottleneck is the transformation which has a cost of O(N2log2 N) using the fast Fourier transform (FFT). However, the increase in efficiency is less significant when Ngg n as is the case in CNNs. We mitigate this by using the "overlap-and-add" technique reducing the computational complexity to O(N2log2 n) per kernel. This method increases the algorithm's efficiency in both the forward and backward propagation, reducing the training and testing time for CNNs. Our empirical results show our method reduces computational time by a factor of up to 16.3 times the traditional convolution implementation for a 8 × 8 kernel and a 224 × 224 image.