# Weighted sampling of outer products

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2014.

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

- [Quantum Machine Learning For Classical Data](https://mlsanity.com/paper/2105.03684/) (2021)

## Abstract (arXiv)

This note gives a simple analysis of the randomized approximation scheme for matrix multiplication of Drineas et al (2006) with a particular sampling distribution over outer products. The result follows from a matrix version of Bernstein's inequality. To approximate the matrix product AB^top to spectral norm error varepsilon|A||B|, it suffices to sample on the order of (sr(A) vee sr(B)) log(sr(A) wedge sr(B)) / varepsilon2 outer products, where sr(M) is the stable rank of a matrix M.