Research
Random Fourier Features in Near-Linear Time
arXiv:2610.14751v1 Announce Type: new Abstract: Random Fourier features approximate a shift-invariant kernel in R^d, such as the Gaussian kernel exp(-frac12|x-y|_2^2), using independent samples from i
arXiv:2610.14751v1 Announce Type: new Abstract: Random Fourier features approximate a shift-invariant kernel in R^d, such as the Gaussian kernel exp(-frac12|x-y|_2^2), 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, Sarlos and Smola (ICML 2013), using Brascamp-Lieb inequalities and the Schoenberg representation of radial kernels.
Related
- Random features for Grassmannian kernel approximation with bounded rank-one projections
- Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features
- Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization
Source: arXiv cs.LG | 2026-10-14