Fast Summation of Radial Kernels via QMC Slicing

Johannes Hertrich, Tim Jahn, Michael Quellmalz
2/12/2026

No official code found. Best implementation: johertrich/fastsum_QMC_slicing (1 star, MIT, last commit 2025-02-11).

Abstract

The fast computation of large kernel sums is a challenging task, which arises as a subproblem in any kernel method. We approach the problem by slicing, which relies on random projections to one-dimensional subspaces and fast Fourier summation. We prove bounds for the slicing error and propose a quasi-Monte Carlo (QMC) approach for selecting the projections based on spherical quadrature rules. Numerical examples demonstrate that our QMC-slicing approach significantly outperforms existing methods like (QMC-)random Fourier features, orthogonal Fourier features or non-QMC slicing on standard test datasets.

View on arXivView PDF

Code Implementations(1)

johertrich/fastsum_QMC_slicingCommunity64%
MIT

Fast Summation of Radial Kernels via QMC Slicing

10Julia, PythonSep 12, 20241 years agoMIT

Similar Papers

Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms

84% match1 repo22024

Kernel Quadrature with Randomly Pivoted Cholesky

80% match1 repo12026

On the design of scalable, high-precision spherical-radial Fourier features

77% match1 repo2024

Mercer Large-Scale Kernel Machines from Ridge Function Perspective

77% match2023

Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton

76% match2026

Quasi-Monte Carlo for 3D Sliced Wasserstein

76% match1 repo82026

Cite this paper

@article{hertrich2026fast,
  title  = {Fast Summation of Radial Kernels via QMC Slicing},
  author = {Johannes Hertrich and Tim Jahn and Michael Quellmalz},
  year   = {2026},
  eprint = {2410.01316},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2410.01316},
  journal = {ICLR 2024 2024}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2410.01316.svg)](https://codeofpaper.com/paper/2410.01316)

Discussion