ICLR 2025poster6 citations
Fast Summation of Radial Kernels via QMC Slicing
Johannes Hertrich, Tim Jahn, Michael Quellmalz
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.
fast kernel summationslicingquasi-Monte Carlonon-equispaced fast Fourier transformsrandom Fourier features
BibTeX
@inproceedings{
hertrich2025fast,
title={Fast Summation of Radial Kernels via {QMC} Slicing},
author={Johannes Hertrich and Tim Jahn and Michael Quellmalz},
booktitle={The Thirteenth International Conference on Learning Representations},
year={2025},
url={https://openreview.net/forum?id=iNmVX9lx9l}
}