Approximate Matrix–Vectors Under a Bounded ${\ell }_1$ Assumption and Applications to Kernel Matrices

Matrix-vector products (MVPs) are a key primitive in numerical linear algebra and machine learning. However, the naive quadratic running time for exact computation is prohibitive for large matrices, motivating approximate methods. In this paper, we study approximate MVPs under a natural “lightness” assumption, which bounds the total ${\ell }_1$-mass of a $n\times n$ input matrix $A$ by $\gamma n$. For general matrices, we give an algorithm for approximating $Ax$ up to additive $ϵ\Vert x{\Vert }_2$ error in $O(\gamma n^{1.5}/ϵ)$ query time and polynomial preprocessing. We extend this algorithm to kernel matrices by establishing a black-box reduction to Kernel Density Estimation data structures and analyzing a noisy entry sampling scheme. For kernel matrices, our algorithm does not require any preprocessing and improves the best-known running times for Gaussian kernel matrices of [Indyk, Kapralov, Sheth, Wagner; ICLR `25] by polynomial factors in $n$ and $1/ϵ$, and also provides the first algorithms leveraging the lightness assumption for other kernel functions as well.