# Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 85 references that are in the map.
- First posted on arXiv 1 Dec 2022.

## Builds on (most cited first, 30 of 31)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (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)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [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)
- [Size bounds and query plans for relational joins](https://mlsanity.com/paper/1711.03860/) (2017)
- [Testing Graph Clusterability: Algorithms and Lower Bounds](https://mlsanity.com/paper/1808.04807/) (2018)
- [Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap](https://mlsanity.com/paper/1301.5584/) (2013)
- [Improved Coresets for Kernel Density Estimates](https://mlsanity.com/paper/1710.04325/) (2017)
- [Faster Kernel Matrix Algebra via Density Estimation](https://mlsanity.com/paper/2102.08341/) (2021)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [Testing Cluster Structure of Graphs](https://mlsanity.com/paper/1504.03294/) (2015)
- [Approximating the Spectrum of a Graph](https://mlsanity.com/paper/1712.01725/) (2017)
- [Sublinear Time Eigenvalue Approximation via Random Sampling](https://mlsanity.com/paper/2109.07647/) (2021)
- [Approximately Counting Triangles in Sublinear Time](https://mlsanity.com/paper/1504.00954/) (2015)
- [Densest Subgraph in Dynamic Graph Streams](https://mlsanity.com/paper/1506.04417/) (2015)
- [Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs](https://mlsanity.com/paper/1904.09710/) (2019)
- [Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation](https://mlsanity.com/paper/1912.04177/) (2019)
- [Optimal Coreset for Gaussian Kernel Density Estimation](https://mlsanity.com/paper/2007.08031/) (2020)
- [Spectral Clustering Oracles in Sublinear Time](https://mlsanity.com/paper/2101.05549/) (2021)
- [Spectral concentration and greedy k-clustering](https://mlsanity.com/paper/1404.1008/) (2014)

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

- [Improved Space Bounds for Learning with Experts](https://mlsanity.com/paper/2303.01453/) (2023)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)

## Abstract (arXiv)

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given n input points, most kernel-based algorithms need to materialize the full n × n kernel matrix before performing any subsequent computation, thus incurring Omega(n2) runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain textitsubquadratic time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in n) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from textitweighted vertex and textitweighted edge sampling on kernel graphs, textitsimulating random walks on kernel graphs, and textitimportance sampling on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in textitsublinear (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a 9x decrease in the number of kernel evaluations over baselines for LRA and a 41x reduction in the graph size for spectral sparsification.