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 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 one-dimensional setting. Second, for solving these one-dimensional problems efficiently, we apply fast Fourier summations on non-equispaced 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 dimension-independent error bound and represent its one-dimensional counterpart via a closed-form Fourier transform. We provide a run time comparison and error estimate of our fast kernel summations.

本文提出了一种近似过程以降低基于核的方法中$O(N^2)$复杂度到$O(N)$，通过分析基础函数的切片版本将任何径向核表示为一维核，并且导出了一维核的解析公式。通过广义Riemann-Liouville分数积分，我们可以将$d$维核求和降低为一维设置。为了高效地解决这些一维问题，我们采用快速傅里叶求和在非等距数据上的排序算法或两者的组合。对于高斯核，我们展示了一个与维度无关的误差界限，并通过闭式傅立叶变换表示其一维对应物。同时给出了我们的快速核求和的运行时间比较和误差估计。

高维情况下通过切片和傅立叶变换进行快速核求和