Faster Kernel Matrix Algebra via Density Estimation - Backurs, Arturs; Indyk, Piotr; Musco, Cameron; Wagner, Tal (2021)
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.