@inproceedings{backurs2021faster,
author = {Backurs, Arturs and Indyk, Piotr and Musco, Cameron and Wagner, Tal},
title = {Faster Kernel Matrix Algebra via Density Estimation},
year = {2021},
month = {July},
abstract = {We study fast algorithms for computing fundamental properties of a positive semidefinite kernel matrix K in R^[n x n] corresponding to n points x_1, ..., x_n in 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+eps 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+eps 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/faster-kernel-matrix-algebra-via-density-estimation/},
}