# Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 69 references that are in the map.
- First posted on arXiv 16 Jan 2024.

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

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [Generalized Sliced Wasserstein Distances](https://mlsanity.com/paper/1902.00434/) (2019)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Maximum Mean Discrepancy Gradient Flow](https://mlsanity.com/paper/1906.04370/) (2019)
- [Kernel Operations on the GPU, with Autodiff, without Memory Overflows](https://mlsanity.com/paper/2004.11127/) (2020)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Generative Sliced MMD Flows with Riesz Kernels](https://mlsanity.com/paper/2305.11463/) (2023)
- [Posterior Sampling Based on Gradient Flows of the MMD with Negative Distance Kernel](https://mlsanity.com/paper/2310.03054/) (2023)
- [Generalization Bounds for Sparse Random Feature Expansions](https://mlsanity.com/paper/2103.03191/) (2021)
- [Wasserstein Steepest Descent Flows of Discrepancies with Riesz Kernels](https://mlsanity.com/paper/2211.01804/) (2022)
- [Nonparametric Generative Modeling with Conditional Sliced-Wasserstein Flows](https://mlsanity.com/paper/2305.02164/) (2023)
- [ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions](https://mlsanity.com/paper/1410.0260/) (2014)
- [Neural Wasserstein Gradient Flows for Maximum Mean Discrepancies with Riesz Kernels](https://mlsanity.com/paper/2301.11624/) (2023)
- [The Fast Kernel Transform](https://mlsanity.com/paper/2106.04487/) (2021)
- [Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations](https://mlsanity.com/paper/1603.08057/) (2016)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Far-Field Compression for Fast Kernel Summation Methods in High Dimensions](https://mlsanity.com/paper/1409.2802/) (2014)

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

- [Fast Summation of Radial Kernels via QMC Slicing](https://mlsanity.com/paper/2410.01316/) (2024)
- [Generative Feature Training of Thin 2-Layer Networks](https://mlsanity.com/paper/2411.06848/) (2024)
- [Smoothed Distance Kernels for MMDs and Applications in Wasserstein Gradient Flows](https://mlsanity.com/paper/2504.07820/) (2025)
- [Sliced ReLU attention: Quasi-linear contextual expressivity via sorting](https://mlsanity.com/paper/2512.11411/) (2025)
- [Neural Fidelity Calibration for Informative Sim-to-Real Adaptation](https://mlsanity.com/paper/2504.08604/) (2025)
- [Fast Gauss Sums via Flash Attention](https://mlsanity.com/paper/2609.04910/) (2026)
- [Quasi Linear Kernel Attention with Infinite Capacity](https://mlsanity.com/paper/2609.35349/) (2026)
- [FlashDiffusion: Fused Tiled Kernel Spectral Decomposition](https://mlsanity.com/paper/2609.38198/) (2026)

## Abstract (arXiv)

Kernel-based methods are heavily used in machine learning. However, they suffer from O(N2) complexity in the number N of considered data points. In this paper, we propose an approximation procedure, which reduces this complexity to O(N). Our approach is based on two ideas. First, we prove that any radial kernel with analytic basis function can be represented as sliced version of some one-dimensional kernel and derive an analytic formula for the one-dimensional counterpart. It turns out that the relation between one- and d-dimensional kernels is given by a generalized Riemann-Liouville fractional integral. Hence, we can reduce the d-dimensional kernel summation to a one-dimensional setting. Second, for solving these one-dimensional problems efficiently, we apply fast Fourier summations on non-equispaced data, a sorting algorithm or a combination of both. Due to its practical importance we pay special attention to the Gaussian kernel, where we show a dimension-independent error bound and represent its one-dimensional counterpart via a closed-form Fourier transform. We provide a run time comparison and error estimate of our fast kernel summations.