Abstract
We explore the redundancy of parameters in deep neural networks by replacing the conventional linear projection in fully-connected layers with the circulant projection. The circulant structure substantially reduces memory footprint and enables the use of the Fast Fourier Transform (FFT) to speed up the computation. Considering a fully-connected neural network layer with $d$ input nodes and $d$ output nodes, this method improves the time complexity from $O(d^2)$ to $O(d \log d)$ and space complexity from $O(d^2)$ to $O(d)$. The space savings are particularly important for modern deep convolutional neural network architectures, where fully-connected layers typically contain more than 90% of the network parameters. We further show that the gradient computation and optimization of the circulant projections can be performed very efficiently. Our experiments on three standard datasets show that the proposed approach achieves this significant gain in storage and efficiency with minimal increase in error rate compared to neural networks with unstructured projections.
Introduction
While convolutional layers handle the bulk of feature extraction in modern Convolutional Neural Networks (CNNs), fully-connected (FC) layers often represent the primary memory bottleneck. In classic architectures like AlexNet, FC layers can account for over 90% of the total model parameters. This "parameter explosion" poses significant challenges for deploying state-of-the-art models on memory-constrained hardware, such as mobile devices, embedded systems, or GPUs with limited VRAM.
Rather than relying on post-hoc compression techniques like pruning, this research investigates whether the massive number of independent weights in FC layers is fundamentally necessary. We propose that these layers are highly redundant and can be replaced by a structured mathematical alternative: the circulant projection.
Methodology: Circulant Neural Networks
The core innovation of this work is the replacement of standard weight matrices with circulant matrices.
The Circulant Matrix
In a standard FC layer, a weight matrix $R \in \mathbb{R}^{d \times d}$ requires $d^2$ independent parameters. In contrast, a circulant matrix is defined by a single vector $r = (r_0, r_1, \dots, r_{d-1})$, where each row is a cyclic shift of the preceding row. This structure reduces the storage requirement from $O(d^2)$ to $O(d)$.
Computational Efficiency via FFT
Multiplying a vector by a circulant matrix is mathematically equivalent to a circular convolution. By leveraging the Fast Fourier Transform (FFT), the computational complexity of the forward pass is reduced from $O(d^2)$ to $O(d \log d)$. Furthermore, we derive gradient identities showing that backpropagation can also be performed entirely in the frequency domain, maintaining these efficiency gains throughout the training process.
The Sign-Flipping Trick
To ensure the circulant projection mimics the properties of a "natural" randomized projection, we introduce a diagonal matrix $D$ containing random $\pm 1$ values. The resulting operation, $h(x) = \phi(RDx)$, utilizes "random sign flipping" to preserve distances and improve performance. Without this component, the effectiveness of circulant layers diminishes significantly.
Experimental Setup
We evaluated the Circulant Neural Network across three standard benchmarks:
- MNIST: Handwritten digit recognition (60,000 training images).
- CIFAR-10: Natural image classification across 10 classes (50,000 images).
- ImageNet (ILSVRC-2010): Large-scale classification using the AlexNet architecture as a baseline.
Key Results and Discussion
The experiments demonstrate that the "intrinsic dimension" of the transformations learned by FC layers is much lower than their parameter counts suggest.
Memory and Accuracy Trade-offs
On the AlexNet architecture, the circulant approach reduced the memory footprint of the FC layers from 233.2 MB to just 20.5 MB. While the specific FC layer parameters were reduced by a factor of 4000x, the overall model size decreased by over 10x.
The impact on accuracy was marginal:
- MNIST: Error rate increased slightly from 0.92% (standard) to 0.95% (circulant).
- ImageNet: Top-5 error increased from 17.1% to 19.4%, a small price for the massive storage reduction.
Data Efficiency and Regularization
As shown in the figures above, circulant networks often require fewer training samples to reach a stable error rate compared to unstructured networks. Because they possess far fewer parameters, circulant layers act as a form of built-in regularization. We observed that standard techniques like dropout were often less necessary, and in some cases, even detrimental to the performance of circulant architectures.
Conclusion
Circulant projections offer a powerful method for reducing parameter redundancy in deep networks. By shifting computation to the frequency domain, we achieve significant gains in both space and time complexity with minimal loss in predictive performance. Future work may involve optimizing custom FFT kernels for specific hardware to realize theoretical speedups in practice.
Summary updated