Even Faster Kernel Matrix Linear Algebra via Density Estimation
By: Rikhav Shah, Sandeep Silwal, Haike Xu
Potential Business Impact:
Speeds up computer math for big data problems.
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 R^d$. 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.
Similar Papers
Wishart kernel density estimation for strongly mixing time series on the cone of positive definite matrices
Methodology
Helps understand financial data better.
A general technique for approximating high-dimensional empirical kernel matrices
Machine Learning (Stat)
Makes computer predictions more accurate for complex data.
Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
Machine Learning (CS)
Finds important patterns in fast-changing data.