Faster Kernel Matrix Algebra via Density Estimation


Event details

Date 25.05.2023
Hour 13:0014:00
Speaker Professor Piotr Indyk - MIT
Category Conferences - Seminars
Event Language French
Computational Mathematics Seminar
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


  • Prof. Daniel Kressner


  • Samantha Bettschen

Event broadcasted in