๐Ÿ“–
Approximate Matrix Multiplication through Joint Leverage Score Sampling
Neophytos Charalambides, Mert Pilanci, Alfred O. Hero

Approximate Matrix Multiplication through Joint Leverage Score Sampling

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Approximate Matrix Multiplication through Joint Leverage Score Sampling
Author / Organization Neophytos Charalambides, Mert Pilanci, Alfred O. Hero
Subject & Discipline math.NA
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-267961
Original Source Link Visit Source Page on arxiv.org »