Analysis of a randomized approximation scheme for matrix multiplication
arXiv:1211.54143 citationsh-index: 97
Originality Synthesis-oriented
AI Analysis
For researchers in randomized linear algebra, this offers a cleaner theoretical justification for an existing method, but is incremental.
The paper provides a simple analysis of a randomized matrix multiplication approximation scheme, proving its accuracy using matrix Bernstein and quadratic form inequalities.
This note gives a simple analysis of a randomized approximation scheme for matrix multiplication proposed by Sarlos (2006) based on a random rotation followed by uniform column sampling. The result follows from a matrix version of Bernstein's inequality and a tail inequality for quadratic forms in subgaussian random vectors.