# Gaussian Quadrature for Kernel Features

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2017.

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

- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Large-Scale Learning with Fourier Features and Tensor Decompositions](https://mlsanity.com/paper/2109.01545/) (2021)
- [No-Regret Algorithms for Private Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2102.12467/) (2021)
- [Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition](https://mlsanity.com/paper/2106.05992/) (2021)
- [Gauss-Legendre Features for Gaussian Process Regression](https://mlsanity.com/paper/2101.01137/) (2021)
- [Spectraformer: A Unified Random Feature Framework for Transformer](https://mlsanity.com/paper/2405.15310/) (2024)
- [Learning nonparametric ordinary differential equations from noisy data](https://mlsanity.com/paper/2206.15215/) (2022)
- [Interpretable Bayesian Tensor Network Kernel Machines with Automatic Rank and Feature Selection](https://mlsanity.com/paper/2507.11136/) (2025)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Kernel Interpolation with Sparse Grids](https://mlsanity.com/paper/2305.14451/) (2023)
- [Trigonometric Quadrature Fourier Features for Scalable Gaussian Process Regression](https://mlsanity.com/paper/2310.14544/) (2023)
- [Variance-Reducing Couplings for Random Features](https://mlsanity.com/paper/2405.16541/) (2024)
- [On the design of scalable, high-precision spherical-radial Fourier features](https://mlsanity.com/paper/2408.13231/) (2024)
- [Feature maps for the Laplacian kernel and its generalizations](https://mlsanity.com/paper/2502.15575/) (2025)
- [Fast Newton method solving KLR based on Multilevel Circulant Matrix with log-linear complexity](https://mlsanity.com/paper/2108.08605/) (2021)
- [Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices](https://mlsanity.com/paper/2408.02346/) (2024)
- [Kernel Operator-Theoretic Bayesian Filter for Nonlinear Dynamical Systems](https://mlsanity.com/paper/2411.00198/) (2024)
- [Kernel Approximation using Analog In-Memory Computing](https://mlsanity.com/paper/2411.03375/) (2024)
- [Scalable Deep Basis Kernel Gaussian Processes](https://mlsanity.com/paper/2505.18526/) (2025)
- [Regular Fourier Features for Nonstationary Gaussian Processes](https://mlsanity.com/paper/2602.23006/) (2026)

## Abstract (arXiv)

Kernel methods have recently attracted resurgent interest, showing performance competitive with deep neural networks in tasks such as speech recognition. The random Fourier features map is a technique commonly used to scale up kernel machines, but employing the randomized feature map means that O(ε-2) samples are required to achieve an approximation error of at most ε. We investigate some alternative schemes for constructing feature maps that are deterministic, rather than random, by approximating the kernel in the frequency domain using Gaussian quadrature. We show that deterministic feature maps can be constructed, for any γ > 0, to achieve error ε with O(eeγ + ε-1/γ) samples as ε goes to 0. Our method works particularly well with sparse ANOVA kernels, which are inspired by the convolutional layer of CNNs. We validate our methods on datasets in different domains, such as MNIST and TIMIT, showing that deterministic features are faster to generate and achieve accuracy comparable to the state-of-the-art kernel methods based on random Fourier features.