Fast Summation of Radial Kernels via QMC Slicing
<|reference_start|>Fast Summation of Radial Kernels via QMC Slicing: 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.<|reference_end|>
@article{hertrich2024fast,
    title={Fast Summation of Radial Kernels via QMC Slicing},
    author={Johannes Hertrich, Tim Jahn, Michael Quellmalz},
    journal={arXiv preprint arXiv:2410.01316},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.01316},
    primaryClass={math.NA cs.LG cs.NA stat.CO stat.ML}
}