An exploration of parameter redundancy in deep networks with circulant projections

Yu Cheng, Felix X. Yu, Rogério Feris, Sanjiv Kumar, Alok Choudhary, Shih‐Fu Chang

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.

Comparison of theoretical complexity between conventional and circulant neural networks.

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.
Error rates as a function of training samples across MNIST, CIFAR-10, and ILSVRC-2010 datasets.

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

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 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(dlogd) 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.
BibTeX
@misc{cheng2015exploration,
  author = {Yu Cheng and Felix X. Yu and Rogério Feris and Sanjiv Kumar and Alok Choudhary and Shih‐Fu Chang},
  title = {{An exploration of parameter redundancy in deep networks with circulant projections}},
  year = {2015},
  eprint = {1502.03436},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1502.03436},
}
Figure