![]() |
ETNA - Electronic Transactions on Numerical Analysis
|
![]() |
Verlag der Österreichischen Akademie der Wissenschaften Austrian Academy of Sciences Press
A-1011 Wien, Dr. Ignaz Seipel-Platz 2
Tel. +43-1-515 81/DW 3420, Fax +43-1-515 81/DW 3400 https://verlag.oeaw.ac.at, e-mail: verlag@oeaw.ac.at |
|
||||||||||||||||||||
|
DATUM, UNTERSCHRIFT / DATE, SIGNATURE
BANK AUSTRIA CREDITANSTALT, WIEN (IBAN AT04 1100 0006 2280 0100, BIC BKAUATWW), DEUTSCHE BANK MÜNCHEN (IBAN DE16 7007 0024 0238 8270 00, BIC DEUTDEDBMUC)
|

ETNA - Electronic Transactions on Numerical Analysis, pp. 496-539, 2025/11/11
One of the main computational bottlenecks in kernel-based learning is to cope 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 lie in higher-dimensional feature spaces. Here we present a technique together with a rigorous error analysis based on the non-equispaced fast Fourier transform (NFFT) that allows fast and accurate approximations of the matrix-vector product with the resulting kernel matrices. We show that this approach is also well suited for 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. In the numerical experiments, we illustrate the performance of the additive kernel scheme with Fourier-based fast matrix-vector products on a number of data sets when using kernel ridge regression.
Keywords: additive kernels, feature grouping, Fourier analysis, kernel derivatives, multiple kernel learning