Even Faster Kernel Matrix Linear Algebra via Density Estimation

• URL: http://arxiv.org/abs/2510.02540v1
• Date: Thu, 02 Oct 2025 20:15:38 GMT
• Title: Even Faster Kernel Matrix Linear Algebra via Density Estimation
• Authors: Rikhav Shah, Sandeep Silwal, Haike Xu,
• Abstract summary: We use kernel density estimation (KDE) for linear algebraic tasks involving the kernel matrix of a collection of $n$ data points in $mathbb Rd$.<n>Our improvements over existing best algorithms reduce the dependence on $varepsilon$, and additionally decreases the dependence on $n$ in the case of computing the sum of all entries of the kernel matrix.
• Score: 12.345340809407617
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions [23.539428616884035]
  We study fast algorithms for computing matrix-vector products for asymmetric Gaussian Kernel matrices $Kin mathbbRntimes n$.<n>Our algorithms rely on the following modelling assumption about the $K$: the sum of the entries of $K$ scales linearly in $n$, as opposed to the worst case growth.<n>We obtain the first subquadratic-time algorithm that works under this assumption, for unrestricted computation.
  arXiv  Detail & Related papers  (2025-07-31T13:29:43Z)
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  We give a new family of upper-time algorithms which can certify bounds on the maximum of $|M u|$.<n>Our certification algorithm makes essential use of the Sum-of-Squares hierarchy.
  arXiv  Detail & Related papers  (2024-12-30T18:59:46Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation [24.166833799353476]
  We develop efficient reductions from $textitweighted edge sampling$ on kernel graphs, $textitsimulating random walks$ on kernel graphs, and $textitweighted sampling$ on matrices to Kernel Density Estimation. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest.
  arXiv  Detail & Related papers  (2022-12-01T16:42:56Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  We give an input sparsity time sampling algorithm for approximating the Gram matrix corresponding to the $q$-fold column-wise tensor product of $q$ matrices. Our sampling technique relies on a collection of $q$ partially correlated random projections which can be simultaneously applied to a dataset $X$ in total time.
  arXiv  Detail & Related papers  (2022-02-09T15:26:03Z)
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra [6.338178373376447]
  We propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. Our method can improve the runtime of solving quantum linear systems of dimension $N$ to $O(kappa operatornamepolylog(fracNvarepsilon))$.
  arXiv  Detail & Related papers  (2022-01-27T05:24:02Z)
• Faster Kernel Matrix Algebra via Density Estimation [46.253698241653254]
  We study fast algorithms for computing fundamental properties of a positive semidefinite kernel matrix $K in mathbbRn times n$ corresponding to $n$ points.
  arXiv  Detail & Related papers  (2021-02-16T18:25:47Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.