# Random Fourier Features in Near-Linear Time

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 10 Oct 2026.

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

- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [Quadrature-based features for kernel approximation](https://mlsanity.com/paper/1802.03832/) (2018)
- [The Bernstein Mechanism: Function Release under Differential Privacy](https://mlsanity.com/paper/1507.04499/) (2015)
- [Recycling Randomness with Structure for Sublinear time Kernel Expansions](https://mlsanity.com/paper/1605.09049/) (2016)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Scalable Unsupervised Segmentation via Random Fourier Feature-based Gaussian Process](https://mlsanity.com/paper/2507.10632/) (2025)
- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)
- [Flexformer: Flexible Linear Transformer with Learnable Attention Kernel](https://mlsanity.com/paper/2606.27748/) (2026)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)

## Abstract (arXiv)

Random Fourier features approximate a shift-invariant kernel in ℝd, such as the Gaussian kernel exp(-tfrac12|x-y|22), using independent samples from its spectral measure to construct an unbiased estimator for the kernel value with subgaussian concentration. However, generating m such features requires O(md) time. A long line of work on structured random features has accelerated this computation for the Gaussian kernel and other radial kernels, albeit with weaker concentration guarantees. We close this gap by showing a random feature map that can be computed in near-linear time O((d+m)log d) and yields near-subgaussian concentration. We obtain it through a new and tighter analysis of the Fastfood feature map of Le, Sarl'os and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.