Faster Kernel Matrix Algebra via Density Estimation
Event details
| Date | 25.05.2023 |
| Hour | 13:00 › 14:00 |
| Speaker | Professor Piotr Indyk - MIT |
| Location | |
| Category | Conferences - Seminars |
| Event Language | French |
Computational Mathematics Seminar
Abstract :
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency – given n input points, most kernel-based algorithms need to materialize the full n × n kernel matrix before performing any subsequent computation, thus incurring
Ω(n^2) runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts.
In this talk I will present fast algorithms for computing basic properties of an nxn positive semidefinite kernel matrices K, induced by n points x_1,..., x_n in R^d. This includes estimating the sum of kernel matrix entries, computing its top eigenvalue and eigenvector, spectral sparsification, low-rank approximation, etc. The algorithms leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation.
Abstract :
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency – given n input points, most kernel-based algorithms need to materialize the full n × n kernel matrix before performing any subsequent computation, thus incurring
Ω(n^2) runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts.
In this talk I will present fast algorithms for computing basic properties of an nxn positive semidefinite kernel matrices K, induced by n points x_1,..., x_n in R^d. This includes estimating the sum of kernel matrix entries, computing its top eigenvalue and eigenvector, spectral sparsification, low-rank approximation, etc. The algorithms leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation.
Practical information
- General public
- Free
Organizer
- Prof. Daniel Kressner
Contact
- Samantha Bettschen