Hertrich, Johannes;
(2024)
Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms.
SIAM Journal on Mathematics of Data Science (SIMODS)
, 6
(4)
pp. 1109-1137.
10.1137/24M1632085.
Preview |
Text
Hertrich_24m1632085.pdf Download (1MB) | Preview |
Abstract
Kernel-based methods are heavily used in machine learning. However, they suffer from O(N 2 ) complexity in the number N of considered data points. In this paper, we propose an approximation procedure, which reduces this complexity to O(N). Our approach is based on two ideas. First, we prove that any radial kernel with an analytic basis function can be represented as sliced version of some one-dimensional kernel and derive an analytic formula for the one-dimensional counterpart. It turns out that the relation between one- and d-dimensional kernels is given by a generalized Riemann-- Liouville fractional integral. Hence, we can reduce the d-dimensional kernel summation to a onedimensional setting. Second, for solving these one-dimensional problems efficiently, we apply fast Fourier summations on nonequispaced data, a sorting algorithm, or a combination of both. Due to its practical importance we pay special attention to the Gaussian kernel, where we show a dimensionindependent error bound and represent its one-dimensional counterpart via a closed-form Fourier transform. We provide a runtime comparison and error estimate of our fast kernel summations.
| Type: | Article |
|---|---|
| Title: | Fast Kernel Summation in High Dimensions via Slicing and Fourier Transforms |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/24M1632085 |
| Publisher version: | https://doi.org/10.1137/24M1632085 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | fast kernel summation, slicing, nonequispaced Fourier transforms |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10199851 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
