MATH Seminar

Title: How to accelerate learning tasks on big data with ANOVA-based NFFT matrix vector products
Seminar: Numerical Analysis and Scientific Computing
Speaker: Theresa Wagner of University of Technology Chemnitz
Contact: Matthias Chung,
Date: 2023-09-07 at 10:00AM
Venue: MSC N306
Download Flyer
Kernel matrices are crucial in many learning tasks and typically dense and large-scale. Depending on their dimension even computing all their entries is challenging and the cost of matrix vector products scales quadratically with the dimension, if no customized methods are applied. We present a matrix-free approach that exploits the computational power of the non-equispaced fast Fourier transform (NFFT) and is of linear complexity for fixed accuracy. The ANOVA kernel has proved to be a viable tool to group the features into smaller pieces that are then amenable to the NFFT-based summation technique. Multiple kernels based on lower-dimensional feature spaces are combined, such that kernel vector products can be realized by this fast approximation algorithm. Based on a feature grouping approach this can be embedded into a CG or GMRES solver within a learning method and we nearly reach a linear scaling. This approach enables to run learning tasks using kernel methods for large-scale data on a standard laptop computer in reasonable time without or very benign loss of accuracy. It can be embedded into methods that rely on kernel matrices or even graph Laplacians. In this talk, I will demonstrate how kernel ridge regression and support vector machine tasks can benefit from having the fast matrix vector products available and will give an outlook on further applications. This is joint work with Martin Stoll, Franziska Nestler, and John Pearson.

See All Seminars