PreprintCC BY 4.0arXiv
Approximate Matrix Multiplication through Joint Leverage Score Sampling
Abstract
In this paper, we investigate approximate matrix multiplication through random sampling. Specifically, we propose using a non-uniform sampling distribution constructed from the leverage scores of the two matrices, and characterize the associated approximation error in terms of the matrix spectral norm; which is well-known to better characterize the downstream error when the matrix product operator is applied to an input vector. We provide the probability error bounds for the proposed algorithm are also given, and discuss connections to data-oblivious approximate matrix multiplication, and graph sparsification algorithms.
Related
- Fast and Stable Arbitrary Precision Approximate Matrix Multiplication
- Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
- Tensor Degenerations for Matrix Multiplication
- Bi-Oriented Interlaced Matrix Multiplication and an Operator Factorisation of the Quantum Harmonic Oscillator
- Improved Degree Tables for Secure Distributed Matrix Multiplication
BibTeX
@misc{charalambides2026approximate,
title = {{Approximate Matrix Multiplication through Joint Leverage Score Sampling}},
author = {Neophytos Charalambides and Mert Pilanci and Alfred O. Hero III},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29466},
eprint = {2610.29466},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29466},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Approximate Matrix Multiplication through Joint Leverage Score Sampling
AU - Neophytos Charalambides
AU - Mert Pilanci
AU - Alfred O. Hero III
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29466
UR - https://arxiv.org/abs/2610.29466
AB - In this paper, we investigate approximate matrix multiplication through random sampling. Specifically, we propose using a non-uniform sampling distribution constructed from the leverage scores of the two matrices, and characterize the associated approximation error in terms of the matrix spectral norm; which is well-known to better characterize the downstream error when the matrix product operator is applied to an input vector. We provide the probability error bounds for the proposed algorithm are also given, and discuss connections to data-oblivious approximate matrix multiplication, and graph sparsification algorithms.
ER -