One of the main computational bottlenecks when working with kernel based learning is dealing with the large and typically dense kernel matrix. Techniques dealing with fast approximations of the matrix vector product for these kernel matrices typically deteriorate in their performance if the feature vectors reside in higher-dimensional feature spaces. We here present a technique based on the non-equispaced fast Fourier transform (NFFT) with rigorous error analysis. We show that this approach is also well suited to allow the approximation of the matrix that arises when the kernel is differentiated with respect to the kernel hyperparameters; a problem often found in the training phase of methods such as Gaussian processes. We also provide an error analysis for this case. We illustrate the performance of the additive kernel scheme with fast matrix vector products on a number of data sets. Our code is available at https://github.com/wagnertheresa/NFFTAddKer

通过非均匀快速傅里叶变换（NFFT）和严格的误差分析，研究了在处理大型稠密核矩阵时的快速近似方法，以及在高维特征空间中处理核函数导数时的适用性和性能。通过在多个数据集上进行性能演示，验证了加性核方案的有效性。

加性核的快速评估：特征排列、傅立叶方法和核导数