Faster Kernel Matrix Algebra via Density Estimation
This work addresses computational bottlenecks in kernel methods for machine learning practitioners, offering faster algorithms for key matrix operations.
The paper tackles the problem of efficiently computing properties of positive semidefinite kernel matrices, such as the sum of entries and top eigenvalue/eigenvector, by developing algorithms that achieve 1+ε relative error with sublinear or subquadratic time in n and linear in d for popular kernels like Gaussian, exponential, and rational quadratic.
We study fast algorithms for computing fundamental properties of a positive semidefinite kernel matrix $K \in \mathbb{R}^{n \times n}$ corresponding to $n$ points $x_1,\ldots,x_n \in \mathbb{R}^d$. In particular, we consider estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. We show that the sum of matrix entries can be estimated to $1+ε$ relative error in time $sublinear$ in $n$ and linear in $d$ for many popular kernels, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and an approximate eigenvector) can be approximated to $1+ε$ relative error in time $subquadratic$ in $n$ and linear in $d$. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation.