Topinformationen

WS 2024/25

alle Vorträge siehe hier

22.01.2025 um 17:15 Uhr in Raum 69/125

Dr. Michael Quellmalz (TU Berlin)

High-Dimensional Radial Kernels via Slicing

The fast computation of large kernel sums is a challenging task, which arises as a subproblem in any kernel method, including kernel density estimation, electrostatic particle simulation or gradient flows. The complexity of the exact computation is the product of the number of input and output points. In low dimensions, there is a rich literature on fast approximation algorithms. In high dimensions, random Fourier features (RFF) are frequently applied.
We approach the problem by slicing, which relies on projections to one-dimensional subspaces and fast Fourier summation. The sliced kernels are obtained by solving an Abel-type integral equation closely related to the Radon transform. We provide 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.