# The Fast Kernel Transform

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 58 references that are in the map.
- First posted on arXiv 8 Jun 2021.

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

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Distributed Gaussian Processes](https://mlsanity.com/paper/1502.02843/) (2015)
- [Scalable Log Determinants for Gaussian Process Kernel Learning](https://mlsanity.com/paper/1711.03481/) (2017)
- [Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations](https://mlsanity.com/paper/1603.08057/) (2016)
- [Hierarchically Compositional Kernels for Scalable Nonparametric Learning](https://mlsanity.com/paper/1608.00860/) (2016)

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

- [Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation](https://mlsanity.com/paper/2206.08366/) (2022)
- [Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms](https://mlsanity.com/paper/2401.08260/) (2024)
- [Fast Summation of Radial Kernels via QMC Slicing](https://mlsanity.com/paper/2410.01316/) (2024)
- [Scalable Gaussian Processes with Latent Kronecker Structure](https://mlsanity.com/paper/2506.06895/) (2025)
- [Learnable Faster Kernel-PCA for Nonlinear Fault Detection: Deep Autoencoder-Based Realization](https://mlsanity.com/paper/2112.04193/) (2021)
- [Linear Time Kernel Matrix Approximation via Hyperspherical Harmonics](https://mlsanity.com/paper/2202.03655/) (2022)
- [Fast Gaussian process inference by exact Mat'ern kernel decomposition](https://mlsanity.com/paper/2508.01864/) (2025)
- [ibUMAP: Coherent and Scalable Field Evaluation for UMAP Optimization](https://mlsanity.com/paper/2610.01445/) (2026)

## Abstract (arXiv)

Kernel methods are a highly effective and widely used collection of modern machine learning algorithms. A fundamental limitation of virtually all such methods are computations involving the kernel matrix that naively scale quadratically (e.g., constructing the kernel matrix and matrix-vector multiplication) or cubically (solving linear systems) with the size of the data set N. We propose the Fast Kernel Transform (FKT), a general algorithm to compute matrix-vector multiplications (MVMs) for datasets in moderate dimensions with quasilinear complexity. Typically, analytically grounded fast multiplication methods require specialized development for specific kernels. In contrast, our scheme is based on auto-differentiation and automated symbolic computations that leverage the analytical structure of the underlying kernel. This allows the FKT to be easily applied to a broad class of kernels, including Gaussian, Matern, and Rational Quadratic covariance functions and physically motivated Green's functions, including those of the Laplace and Helmholtz equations. Furthermore, the FKT maintains a high, quantifiable, and controllable level of accuracy -- properties that many acceleration methods lack. We illustrate the efficacy and versatility of the FKT by providing timing and accuracy benchmarks and by applying it to scale the stochastic neighborhood embedding (t-SNE) and Gaussian processes to large real-world data sets.