Abstract
Deep neural networks (DNNs) have achieved state-of-the-art performance across various domains, yet their deployment on resource-constrained edge devices is often hindered by significant memory and computational requirements. This paper investigates a novel compression strategy that utilizes Kac’s random walk matrices within a hashing pipeline to reduce the dimensionality of fully connected layers. By replacing traditional Gaussian random matrices with structured rotations that can be computed efficiently in $O(n \log n)$ time, the proposed method offers a memory-efficient alternative for model compression. Evaluations on the MNIST dataset indicate that the Kac-based pipeline maintains competitive classification accuracy, even under substantial dimensionality reduction, providing a promising path for efficient DNN deployment.
Introduction
The rapid advancement of deep learning has come with a substantial "computational tax." Modern models, particularly those with numerous fully connected layers, require immense storage and processing power. In many architectures, these dense layers can account for over 90% of the total model parameters. To facilitate the execution of these models on edge devices such as smartphones or autonomous robots, researchers employ dimensionality reduction techniques.
A prevalent method is "hashing," which projects high-dimensional data into a lower-dimensional space using random matrices. However, the storage of truly random (unstructured) matrices is itself a memory-intensive task, often defeating the purpose of compression. The challenge lies in identifying "pseudo-random" structured matrices that are computationally efficient and easy to store while preserving the critical geometric relationships—such as angular distance—between data points.
Methodology
The authors evaluate several hashing pipelines that utilize a random projection followed by a non-linear sign function to compress data. The study compares three primary approaches:
- Unstructured Matrices: Standard Gaussian random matrices serve as the baseline. While effective at preserving data structure, they are memory-inefficient ($O(n^2)$ storage).
- Structured Matrices (Circulant & Toeplitz): These matrices are defined by a single vector that is shifted or rotated, reducing storage requirements to $O(n)$.
- The Kac Pipeline: The primary contribution of this work is the adaptation of the "Extended $\Psi$-regular hashing" pipeline by substituting the standard Hadamard-Diagonal ($HD$) block with Kac’s random walk matrix ($M$).
Kac’s matrix is constructed through a sequence of $k$ random rotations ($B_i$), where each rotation modifies only two dimensions at a time. Theoretical insights suggest that after $n \log n$ steps, this process converges to a "steady state" that effectively mimics a random rotation. This mathematical property makes it an ideal candidate for efficient data compression.
Experimental Setup
The researchers utilized the MNIST dataset, a standard benchmark consisting of 70,000 grayscale images of handwritten digits. The hashing pipelines were integrated into a Convolutional Neural Network (CNN) architecture, with the compression step positioned immediately preceding the first fully connected layer.
Results and Analysis
The experimental results demonstrate that structured hashing pipelines are highly effective at maintaining model performance under compression.
- High Compression with Minimal Accuracy Loss: All tested pipelines maintained approximately 95% accuracy even when the dimensionality was reduced by 75% (from 1568 to 392 dimensions).
- Comparative Performance of Kac Matrices: The Kac-based pipeline performed on par with established state-of-the-art methods. For instance, at a compression factor of 2, the Kac-Circulant pipeline achieved 96.15% accuracy, nearly identical to the 96.22% achieved by the standard Extended $\Psi$-regular pipeline.
- Robustness to Extreme Reduction: As shown in the performance trends, while some methods experienced sharp declines in accuracy at extreme compression levels (e.g., 32x reduction), the "Extended" versions of the pipelines—including those utilizing Kac matrices—exhibited greater robustness compared to "Short" versions.
Conclusion and Future Work
This study highlights the potential of Kac’s random walk matrices as a computationally efficient tool for DNN compression. By preserving angular distances through structured rotations, the proposed pipeline achieves significant dimensionality reduction with minimal impact on classification performance.
Future research will focus on validating these findings on more complex datasets, such as CIFAR-10 or ImageNet, to assess the scalability of the Kac-based approach. Additionally, the authors aim to bridge the current theoretical gap by providing formal guarantees for the performance of this specific hashing pipeline. Finally, hardware-level optimizations, such as the integration of Fast-Fourier Transforms (FFT), could further enhance the training and inference speeds of these compressed models.
Summary updated