# Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation

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

## Key facts

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

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

- [Low-Precision Arithmetic for Fast Gaussian Processes](https://mlsanity.com/paper/2207.06856/) (2022)
- [One Loss for Quantization: Deep Hashing with Discrete Wasserstein Distributional Matching](https://mlsanity.com/paper/2205.15721/) (2022)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Random matrices in service of ML footprint: ternary random features with no performance loss](https://mlsanity.com/paper/2110.01899/) (2021)
- [Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features](https://mlsanity.com/paper/2106.02614/) (2021)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Error Estimation for Random Fourier Features](https://mlsanity.com/paper/2302.11174/) (2023)

## Abstract (arXiv)

We investigate how to train kernel approximation methods that generalize well under a memory budget. Building on recent theoretical work, we define a measure of kernel approximation error which we find to be more predictive of the empirical generalization performance of kernel approximation methods than conventional metrics. An important consequence of this definition is that a kernel approximation matrix must be high rank to attain close approximation. Because storing a high-rank approximation is memory intensive, we propose using a low-precision quantization of random Fourier features (LP-RFFs) to build a high-rank approximation under a memory budget. Theoretically, we show quantization has a negligible effect on generalization performance in important settings. Empirically, we demonstrate across four benchmark datasets that LP-RFFs can match the performance of full-precision RFFs and the Nystr"om method, with 3x-10x and 50x-460x less memory, respectively.