# A Note on Random Sampling for Matrix Multiplication

arXiv: https://arxiv.org/abs/1811.11237 · HTML: https://mlsanity.com/paper/1811.11237/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2018.

## Built on by (most cited first, 2 of 2)

- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values](https://mlsanity.com/paper/2410.08336/) (2024)

## Abstract (arXiv)

This paper extends the framework of randomised matrix multiplication to a coarser partition and proposes an algorithm as a complement to the classical algorithm, especially when the optimal probability distribution of the latter one is closed to uniform. The new algorithm increases the likelihood of getting a small approximation error in 2-norm and has the squared approximation error in Frobenious norm bounded by that from the classical algorithm.