# Random matrices in service of ML footprint: ternary random features with no performance loss

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 77 references that are in the map.
- First posted on arXiv 5 Oct 2021.

## Builds on (most cited first, 30 of 39)

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Deep Learning with Limited Numerical Precision](https://mlsanity.com/paper/1502.02551/) (2015)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Gaussian Process Behaviour in Wide Deep Neural Networks](https://mlsanity.com/paper/1804.11271/) (2018)
- [High-dimensional dynamics of generalization error in neural networks](https://mlsanity.com/paper/1710.03667/) (2017)
- [Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning](https://mlsanity.com/paper/1810.01075/) (2018)
- [Trained Ternary Quantization](https://mlsanity.com/paper/1612.01064/) (2016)
- [Compressing Deep Convolutional Networks using Vector Quantization](https://mlsanity.com/paper/1412.6115/) (2014)
- [Binary Neural Networks: A Survey](https://mlsanity.com/paper/2004.03333/) (2020)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes](https://mlsanity.com/paper/1810.05148/) (2018)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Traditional and Heavy-Tailed Self Regularization in Neural Network Models](https://mlsanity.com/paper/1901.08276/) (2019)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [A Random Matrix Approach to Neural Networks](https://mlsanity.com/paper/1702.05419/) (2017)
- [Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks](https://mlsanity.com/paper/2005.11879/) (2020)
- [A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent](https://mlsanity.com/paper/2006.05013/) (2020)
- [Implicit Regularization of Random Feature Models](https://mlsanity.com/paper/2002.08404/) (2020)
- [Neural Networks with Few Multiplications](https://mlsanity.com/paper/1510.03009/) (2015)
- [Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixtures](https://mlsanity.com/paper/2001.08370/) (2020)
- [Kernel regression in high dimensions: Refined analysis beyond double descent](https://mlsanity.com/paper/2010.02681/) (2020)
- [Exact expressions for double descent and implicit regularization via surrogate random design](https://mlsanity.com/paper/1912.04533/) (2019)

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

- [Largest Eigenvalues of the Conjugate Kernel of Single-Layered Neural Networks](https://mlsanity.com/paper/2201.04753/) (2022)
- [Overparameterized random feature regression with nearly orthogonal data](https://mlsanity.com/paper/2211.06077/) (2022)
- [Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption](https://mlsanity.com/paper/2310.13434/) (2023)
- [Deep Equilibrium Models are Almost Equivalent to Not-so-deep Explicit Models for High-dimensional Gaussian Mixtures](https://mlsanity.com/paper/2402.02697/) (2024)
- ["Lossless" Compression of Deep Neural Networks: A High-dimensional Neural Tangent Kernel Approach](https://mlsanity.com/paper/2403.00258/) (2024)
- [Deep Neural Network Models Trained With A Fixed Random Classifier Transfer Better Across Domains](https://mlsanity.com/paper/2402.18614/) (2024)
- [On the Equivalence between Implicit and Explicit Neural Networks: A High-dimensional Viewpoint](https://mlsanity.com/paper/2308.16425/) (2023)

## Abstract (arXiv)

In this article, we investigate the spectral behavior of random features kernel matrices of the type bf K = mathbbE_bf w left[σleft(bf wsf Tbf xiright)σleft(bf wsf Tbf xjright)right]i,j=1n, with nonlinear function σ(·), data bf x1, ldots, bf xn ∈ ℝp, and random projection vector bf w ∈ ℝp having i.i.d. entries. In a high-dimensional setting where the number of data n and their dimension p are both large and comparable, we show, under a Gaussian mixture model for the data, that the eigenspectrum of bf K is independent of the distribution of the i.i.d.(zero-mean and unit-variance) entries of bf w, and only depends on σ(·) via its (generalized) Gaussian moments mathbbEz~ mathcal N(0,1)[σ'(z)] and mathbbEz~ mathcal N(0,1)[σ''(z)]. As a result, for any kernel matrix bf K of the form above, we propose a novel random features technique, called Ternary Random Feature (TRF), that (i) asymptotically yields the same limiting kernel as the original bf K in a spectral sense and (ii) can be computed and stored much more efficiently, by wisely tuning (in a data-dependent manner) the function σ and the random vector bf w, both taking values in -1,0,1. The computation of the proposed random features requires no multiplication, and a factor of b times less bits for storage compared to classical random features such as random Fourier features, with b the number of bits to store full precision values. Besides, it appears in our experiments on real data that the substantial gains in computation and storage are accompanied with somewhat improved performances compared to state-of-the-art random features compression/quantization methods.