Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication
This work addresses computational bottlenecks in kernel-based learning methods like support vector machines and kernel ridge regression, offering a domain-specific improvement for high-dimensional data.
The authors tackled the computational challenge of large-scale kernel matrices in high-dimensional feature spaces by proposing an ANOVA kernel with fast matrix-vector multiplication using the non-equispaced fast Fourier transform (NFFT), achieving linear complexity for fixed accuracy and demonstrating performance on several datasets.
Kernel matrices are crucial in many learning tasks such as support vector machines or kernel ridge regression. The kernel matrix is typically dense and large-scale. Depending on the dimension of the feature space even the computation of all of its entries in reasonable time becomes a challenging task. For such dense matrices the cost of a matrix-vector product scales quadratically with the dimensionality N , if no customized methods are applied. We propose the use of an ANOVA kernel, where we construct several kernels based on lower-dimensional feature spaces for which we provide fast algorithms realizing the matrix-vector products. We employ the non-equispaced fast Fourier transform (NFFT), which is of linear complexity for fixed accuracy. Based on a feature grouping approach, we then show how the fast matrix-vector products can be embedded into a learning method choosing kernel ridge regression and the conjugate gradient solver. We illustrate the performance of our approach on several data sets.