# Quantization Algorithms for Random Fourier Features

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 72 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Builds on (most cited first, 13 of 13)

- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Fast Two-Sample Testing with Analytic Representations of Probability Measures](https://mlsanity.com/paper/1506.04725/) (2015)
- [Scalable Kernel Methods via Doubly Stochastic Gradients](https://mlsanity.com/paper/1407.5599/) (2014)
- [Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions](https://mlsanity.com/paper/1511.07130/) (2015)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Experiments with Random Projection](https://mlsanity.com/paper/1301.3849/) (2013)
- [Coding for Random Projections](https://mlsanity.com/paper/1308.2218/) (2013)
- [Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation](https://mlsanity.com/paper/1811.00155/) (2018)
- [Binary and Multi-Bit Coding for Stable Random Projections](https://mlsanity.com/paper/1503.06876/) (2015)
- [Randomized Kernel Multi-view Discriminant Analysis](https://mlsanity.com/paper/2004.01143/) (2020)

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

- [Low-Precision Arithmetic for Fast Gaussian Processes](https://mlsanity.com/paper/2207.06856/) (2022)
- [Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers](https://mlsanity.com/paper/2302.01925/) (2023)
- [Random matrices in service of ML footprint: ternary random features with no performance loss](https://mlsanity.com/paper/2110.01899/) (2021)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference](https://mlsanity.com/paper/2602.07397/) (2026)
- [Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features](https://mlsanity.com/paper/2106.02614/) (2021)
- [Error Estimation for Random Fourier Features](https://mlsanity.com/paper/2302.11174/) (2023)

## Abstract (arXiv)

The method of random projection (RP) is the standard technique in machine learning and many other areas, for dimensionality reduction, approximate near neighbor search, compressed sensing, etc. Basically, RP provides a simple and effective scheme for approximating pairwise inner products and Euclidean distances in massive data. Closely related to RP, the method of random Fourier features (RFF) has also become popular, for approximating the Gaussian kernel. RFF applies a specific nonlinear transformation on the projected data from random projections. In practice, using the (nonlinear) Gaussian kernel often leads to better performance than the linear kernel (inner product), partly due to the tuning parameter (γ) introduced in the Gaussian kernel. Recently, there has been a surge of interest in studying properties of RFF. After random projections, quantization is an important step for efficient data storage, computation, and transmission. Quantization for RP has also been extensive studied in the literature. In this paper, we focus on developing quantization algorithms for RFF. The task is in a sense challenging due to the tuning parameter γ in the Gaussian kernel. For example, the quantizer and the quantized data might be tied to each specific tuning parameter γ. Our contribution begins with an interesting discovery, that the marginal distribution of RFF is actually free of the Gaussian kernel parameter γ. This small finding significantly simplifies the design of the Lloyd-Max (LM) quantization scheme for RFF in that there would be only one LM quantizer for RFF (regardless of γ). We also develop a variant named LM2-RFF quantizer, which in certain cases is more accurate. Experiments confirm that the proposed quantization schemes perform well.