# On The Relative Error of Random Fourier Features for Preserving Kernel Distance

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 68 references that are in the map.
- First posted on arXiv 1 Oct 2022.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [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)
- [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)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Gaussian Quadrature for Kernel Features](https://mlsanity.com/paper/1709.02605/) (2017)
- [Learning to Learn Kernels with Variational Random Features](https://mlsanity.com/paper/2006.06707/) (2020)
- [Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds](https://mlsanity.com/paper/1706.02803/) (2017)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling](https://mlsanity.com/paper/2007.03927/) (2020)
- [Random Fourier Features via Fast Surrogate Leverage Weighted Sampling](https://mlsanity.com/paper/1911.09158/) (2019)
- [Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation](https://mlsanity.com/paper/1811.00155/) (2018)
- [Data-driven Random Fourier Features using Stein Effect](https://mlsanity.com/paper/1705.08525/) (2017)
- [On Data-Dependent Random Features for Improved Generalization in Supervised Learning](https://mlsanity.com/paper/1712.07102/) (2017)
- [Relative Error Embeddings for the Gaussian Kernel Distance](https://mlsanity.com/paper/1602.05350/) (2016)
- [Fast Kernel k-means Clustering Using Incomplete Cholesky Factorization](https://mlsanity.com/paper/2002.02846/) (2020)

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

- [Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms](https://mlsanity.com/paper/2401.08260/) (2024)
- [Enhancing Kernel Power K-means: Scalable and Robust Clustering with Random Fourier Features and Possibilistic Method](https://mlsanity.com/paper/2511.10392/) (2025)

## Abstract (arXiv)

The method of random Fourier features (RFF), proposed in a seminal paper by Rahimi and Recht (NIPS'07), is a powerful technique to find approximate low-dimensional representations of points in (high-dimensional) kernel space, for shift-invariant kernels. While RFF has been analyzed under various notions of error guarantee, the ability to preserve the kernel distance with relative error is less understood. We show that for a significant range of kernels, including the well-known Laplacian kernels, RFF cannot approximate the kernel distance with small relative error using low dimensions. We complement this by showing as long as the shift-invariant kernel is analytic, RFF with poly(ε-1 log n) dimensions achieves ε-relative error for pairwise kernel distance of n points, and the dimension bound is improved to poly(ε-1log k) for the specific application of kernel k-means. Finally, going beyond RFF, we make the first step towards data-oblivious dimension-reduction for general shift-invariant kernels, and we obtain a similar poly(ε-1 log n) dimension bound for Laplacian kernels. We also validate the dimension-error tradeoff of our methods on simulated datasets, and they demonstrate superior performance compared with other popular methods including random-projection and Nystr"om methods.