mlsanityData to 14 Oct 2026

Faster Kernel Matrix Algebra via Density Estimation

arXiv 2102.08341 ↗First posted 16 Feb 2021cs.DS cs.LG cs.NAcited by 8

Not on the map. Why?

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.

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

12 of 31 references.

References · 12

  1. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  2. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 33
  3. 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
  4. 2020Kernel Density Estimation through Density Constrained Near Neighbor Searchcited by 29
  5. 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
  6. 2017Sublinear Time Low-Rank Approximation of Positive Semidefinite Matricescited by 18
  7. 2017On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networkscited by 16
  8. 2019Sample-Optimal Low-Rank Approximation of Distance Matricescited by 15
  9. 2014ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensionscited by 12
  10. 2018Sublinear Time Low-Rank Approximation of Distance Matricescited by 11
  11. 2017Improved Coresets for Kernel Density Estimatescited by 8
  12. 2020Testing Positive Semi-Definiteness via Random Submatricescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 1; 2024: 1; 2025: 2; 2026: 2.

8 papers.

  1. 2023Fast Private Kernel Density Estimation via Locality Sensitive Quantizationcited by 9
  2. 2025Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptionscited by 4
  3. 2022Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimationcited by 2
  4. 2022Giga-scale Kernel Matrix Vector Multiplication on GPUcited by 1
  5. 2025Even Faster Kernel Matrix Linear Algebra via Density Estimationcited by 1
  6. 2026New Bounds for Kernel Sums via Fast Spherical Embeddingscited by 1
  7. 2026Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimationcited by 1
  8. 2024Spectral Toolkit of Algorithms for Graphs: Technical Report (2)cited by 0