# Random Gegenbauer Features for Scalable Kernel Methods

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 45 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Fast DPP Sampling for Nystr"om with Application to Kernel Methods](https://mlsanity.com/paper/1603.06052/) (2016)
- [A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms](https://mlsanity.com/paper/1812.08723/) (2018)
- [Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling](https://mlsanity.com/paper/2007.03927/) (2020)
- [Scaling up Kernel Ridge Regression via Locality Sensitive Hashing](https://mlsanity.com/paper/2003.09756/) (2020)
- [Feature Selection for Ridge Regression with Provable Guarantees](https://mlsanity.com/paper/1506.05173/) (2015)

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

- [Scalable Neural Network Kernels](https://mlsanity.com/paper/2310.13225/) (2023)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [Orthogonal Random Features: Explicit Forms and Sharp Inequalities](https://mlsanity.com/paper/2310.07370/) (2023)
- [Near Optimal Reconstruction of Spherical Harmonic Expansions](https://mlsanity.com/paper/2202.12995/) (2022)
- [RFFNet: Large-Scale Interpretable Kernel Methods via Random Fourier Features](https://mlsanity.com/paper/2211.06410/) (2022)
- [Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization](https://mlsanity.com/paper/2606.11255/) (2026)

## Abstract (arXiv)

We propose efficient random features for approximating a new and rich class of kernel functions that we refer to as Generalized Zonal Kernels (GZK). Our proposed GZK family, generalizes the zonal kernels (i.e., dot-product kernels on the unit sphere) by introducing radial factors in their Gegenbauer series expansion, and includes a wide range of ubiquitous kernel functions such as the entirety of dot-product kernels as well as the Gaussian and the recently introduced Neural Tangent kernels. Interestingly, by exploiting the reproducing property of the Gegenbauer polynomials, we can construct efficient random features for the GZK family based on randomly oriented Gegenbauer kernels. We prove subspace embedding guarantees for our Gegenbauer features which ensures that our features can be used for approximately solving learning problems such as kernel k-means clustering, kernel ridge regression, etc. Empirical results show that our proposed features outperform recent kernel approximation methods.