Weighted sampling of outer products

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.