Faster Kernel Matrix Algebra via Density Estimation

Arturs Backurs, Piotr Indyk, Cameron Musco, Tal Wagner

Abstract

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+\epsilon$ 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+\epsilon$ 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.

Introduction

Kernel methods are a cornerstone of machine learning, powering everything from Support Vector Machines (SVMs) to Gaussian Processes. At their heart lies the kernel matrix $K$, which stores the similarity between every pair of points in a dataset of size $n$. Historically, the primary bottleneck has been efficiency: to even write down the full matrix $K$, one requires $O(n^2)$ time and space. For a dataset with a million points, $n^2$ reaches a trillion entries, making standard matrix algebra impractical on modern hardware.

While researchers have developed fast ways to estimate "kernel density" (the average similarity of a point to a dataset), using those tools to perform fundamental matrix operations like finding the sum of all entries or calculating the top eigenvalue remained an open challenge. This paper breaks the "quadratic barrier" by providing the first sublinear-time algorithm for estimating the sum of kernel matrix entries and the first subquadratic-time algorithm for approximating the top eigenvalue and eigenvector.

Methodology

The authors bridge the gap between Kernel Density Estimation (KDE) and matrix algebra using two primary algorithmic frameworks:

  1. Sublinear Kernel Summation: To estimate the sum of all entries in $K$, the algorithm avoids examining the entire matrix. Instead, it samples a small "principal submatrix" (a subset of rows and columns) of size roughly $O(\sqrt{n} \times \sqrt{n})$. The authors prove a "PSD Mass is Spread Out" lemma, which guarantees that for positive semidefinite (PSD) matrices, the "weight" of the entries is not concentrated in a few small regions, making sampling highly effective.
  2. Kernel Noisy Power Method (KNPM): To find the top eigenvector, the authors adapt the classic Power Method ($z \leftarrow Kz$). Standard matrix-vector multiplication (MVM) takes $O(n^2)$ time. The authors replace this with an approximate MVM powered by fast KDE algorithms.

The Secret Sauce: Standard "noisy" power methods often fail if the noise is biased. However, because most kernels are non-negative, the Perron-Frobenius theorem applies: the top eigenvector is also non-negative. The authors demonstrate that if their KDE-based approximation only overestimates the density, the resulting non-negative noise will not "wash out" the true signal of the top eigenvector, allowing for robust convergence.

Theoretical Complexity and Results

The theoretical improvements are dramatic, particularly for the Gaussian and Exponential kernels. The authors prove that their sampling strategy for sum estimation is mathematically optimal, hitting the $\Omega(\sqrt{n})$ lower bound.

Table 1: Summary of algorithmic runtimes for kernel sum and top eigenvector estimation across different kernel types.

As detailed in the table above, for the Gaussian kernel, sum estimation is achieved in $\tilde{O}(dn^{0.66})$ time, while the top eigenvector is found in $\tilde{O}(dn^{1.173})$ time. These results represent the first significant breach of the $O(n^2)$ quadratic barrier for these fundamental operations.

Empirical Validation

The authors evaluated their algorithms on two well-known benchmarks:

  • Forest Covertype: A 54-dimensional dataset using five specific classes with sizes ranging from 2,700 to 35,700 points.
  • MNIST: The classic handwritten digit dataset, using the full training set of 60,000 points in 784 dimensions.

In these tests, the KNPM algorithm consistently outperformed both the "Full" power method (which is too slow for large $n$) and uniform sampling. It achieved significantly higher accuracy for the same "computational budget," measured by the total number of kernel evaluations.

Conclusion and Future Work

This research demonstrates that matrix algebra can be effectively reframed as a density estimation problem. By leveraging the structural properties of PSD matrices, the authors achieve sublinear and subquadratic runtimes that were previously thought to be unattainable.

Future work remains to close the gap between the current theoretical results and lower bounds. While sum estimation is optimal, there is still a gap for eigenvalues ($\Omega(nd)$ vs. $O(n^{1.173})$). Additionally, extending these KDE-based tricks to find a full low-rank approximation (the top $k$ eigenvectors) for applications like Kernel PCA is a natural next step for the field.

Summary updated

Abstract

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+\epsilon$ 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+\epsilon$ 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.
BibTeX
@inproceedings{backurs2021faster,
  author = {Arturs Backurs and Piotr Indyk and Cameron Musco and Tal Wagner},
  title = {{Faster Kernel Matrix Algebra via Density Estimation}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=8K5DbXfDn4},
}
Figure