# Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 4 Jun 2021.

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

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [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)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Large Scale Kernel Learning using Block Coordinate Descent](https://mlsanity.com/paper/1602.05310/) (2016)
- [Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation](https://mlsanity.com/paper/1811.00155/) (2018)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Faster Binary Embeddings for Preserving Euclidean Distances](https://mlsanity.com/paper/2010.00712/) (2020)
- [Kernel Approximation Methods for Speech Recognition](https://mlsanity.com/paper/1701.03577/) (2017)
- [Data-dependent compression of random features for large-scale kernel approximation](https://mlsanity.com/paper/1810.04249/) (2018)
- [Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines](https://mlsanity.com/paper/2004.06560/) (2020)
- [Fast binary embeddings, and quantized compressed sensing with structured matrices](https://mlsanity.com/paper/1801.08639/) (2018)

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

- [Frame Quantization of Neural Networks](https://mlsanity.com/paper/2404.08131/) (2024)
- [StreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm](https://mlsanity.com/paper/2108.10411/) (2021)

## Abstract (arXiv)

We propose the use of low bit-depth Sigma-Delta and distributed noise-shaping methods for quantizing the Random Fourier features (RFFs) associated with shift-invariant kernels. We prove that our quantized RFFs -- even in the case of 1-bit quantization -- allow a high accuracy approximation of the underlying kernels, and the approximation error decays at least polynomially fast as the dimension of the RFFs increases. We also show that the quantized RFFs can be further compressed, yielding an excellent trade-off between memory use and accuracy. Namely, the approximation error now decays exponentially as a function of the bits used. Moreover, we empirically show by testing the performance of our methods on several machine learning tasks that our method compares favorably to other state of the art quantization methods in this context.