Fast Summation of Radial Kernels via QMC Slicing
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.
Cite
Text
Hertrich et al. "Fast Summation of Radial Kernels via QMC Slicing." International Conference on Learning Representations, 2025.Markdown
[Hertrich et al. "Fast Summation of Radial Kernels via QMC Slicing." International Conference on Learning Representations, 2025.](https://mlanthology.org/iclr/2025/hertrich2025iclr-fast/)BibTeX
@inproceedings{hertrich2025iclr-fast,
title = {{Fast Summation of Radial Kernels via QMC Slicing}},
author = {Hertrich, Johannes and Jahn, Tim and Quellmalz, Michael},
booktitle = {International Conference on Learning Representations},
year = {2025},
url = {https://mlanthology.org/iclr/2025/hertrich2025iclr-fast/}
}