# Even Faster Kernel Matrix Linear Algebra via Density Estimation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 2 Oct 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Stein's Method Meets Computational Statistics: A Review of Some Recent Developments](https://mlsanity.com/paper/2105.03481/) (2021)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Optimal Eigenvalue Approximation via Sketching](https://mlsanity.com/paper/2304.09281/) (2023)
- [Efficiently Computing Similarities to Private Datasets](https://mlsanity.com/paper/2403.08917/) (2024)
- [Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems](https://mlsanity.com/paper/2006.14015/) (2020)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [Sublinear Time Eigenvalue Approximation via Random Sampling](https://mlsanity.com/paper/2109.07647/) (2021)
- [A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations](https://mlsanity.com/paper/2401.02562/) (2024)
- [Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions](https://mlsanity.com/paper/2507.23539/) (2025)
- [Testing Positive Semi-Definiteness via Random Submatrices](https://mlsanity.com/paper/2005.06441/) (2020)
- [Tight Sampling Bounds for Eigenvalue Approximation](https://mlsanity.com/paper/2411.03227/) (2024)

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

- [New Bounds for Kernel Sums via Fast Spherical Embeddings](https://mlsanity.com/paper/2605.01263/) (2026)

## Abstract (arXiv)

This paper studies the use of kernel density estimation (KDE) for linear algebraic tasks involving the kernel matrix of a collection of n data points in mathbb Rd. In particular, we improve upon existing algorithms for computing the following up to (1+varepsilon) relative error: matrix-vector products, matrix-matrix products, the spectral norm, and sum of all entries. The runtimes of our algorithms depend on the dimension d, the number of points n, and the target error varepsilon. Importantly, the dependence on n in each case is far lower when accessing the kernel matrix through KDE queries as opposed to reading individual entries. Our improvements over existing best algorithms (particularly those of Backurs, Indyk, Musco, and Wagner '21) for these tasks reduce the polynomial dependence on varepsilon, and additionally decreases the dependence on n in the case of computing the sum of all entries of the kernel matrix. We complement our upper bounds with several lower bounds for related problems, which provide (conditional) quadratic time hardness results and additionally hint at the limits of KDE based approaches for the problems we study.