# Learning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication

arXiv: https://arxiv.org/abs/2111.10140 · HTML: https://mlsanity.com/paper/2111.10140/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 7 of 7)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions](https://mlsanity.com/paper/1410.0260/) (2014)
- [NFFT meets Krylov methods: Fast matrix-vector products for the graph Laplacian of fully connected networks](https://mlsanity.com/paper/1808.04580/) (2018)
- [A literature survey of matrix methods for data science](https://mlsanity.com/paper/1912.07896/) (2019)
- [Inv-ASKIT: A Parallel Fast Diret Solver for Kernel Matrices](https://mlsanity.com/paper/1602.01376/) (2016)

## Built on by (most cited first, 4 of 4)

- [A Preconditioned Interior Point Method for Support Vector Machines Using an ANOVA-Decomposition and NFFT-Based Matrix-Vector Products](https://mlsanity.com/paper/2312.00538/) (2023)
- [Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives](https://mlsanity.com/paper/2404.17344/) (2024)
- [Fast and interpretable Support Vector Classification based on the truncated ANOVA decomposition](https://mlsanity.com/paper/2402.02438/) (2024)
- [Preconditioned Additive Gaussian Processes with Fourier Acceleration](https://mlsanity.com/paper/2504.00480/) (2025)

## Abstract (arXiv)

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.