# Faster Kernel Matrix Algebra via Density Estimation

arXiv: https://arxiv.org/abs/2102.08341 · HTML: https://mlsanity.com/paper/2102.08341/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 16 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Near-Optimal Coresets of Kernel Density Estimates](https://mlsanity.com/paper/1802.01751/) (2018)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Sample-Optimal Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1906.00339/) (2019)
- [ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions](https://mlsanity.com/paper/1410.0260/) (2014)
- [Sublinear Time Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1809.06986/) (2018)
- [Improved Coresets for Kernel Density Estimates](https://mlsanity.com/paper/1710.04325/) (2017)
- [Testing Positive Semi-Definiteness via Random Submatrices](https://mlsanity.com/paper/2005.06441/) (2020)

## Built on by (most cited first, 8 of 8)

- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions](https://mlsanity.com/paper/2507.23539/) (2025)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Giga-scale Kernel Matrix Vector Multiplication on GPU](https://mlsanity.com/paper/2202.01085/) (2022)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)
- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)
- [Spectral Toolkit of Algorithms for Graphs: Technical Report (2)](https://mlsanity.com/paper/2407.07096/) (2024)

## Abstract (arXiv)

We study fast algorithms for computing fundamental properties of a positive semidefinite kernel matrix K ∈ ℝn × n corresponding to n points x1,ldots,xn ∈ ℝ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.