Improved Sparse Recovery for Approximate Matrix Multiplication

We present a simple randomized algorithm for approximate matrix multiplication (AMM) whose error scales with the output norm $\mathrm{\parallel }AB{\mathrm{\parallel }}_F$. Given any $n\times n$ matrices $A,B$ and a runtime parameter $r\le n$, the algorithm produces in $O(n^2(r+\log n))$ time, a matrix $C$ with total squared error $\mathbb{E}[\mathrm{\parallel }C-AB{\mathrm{\parallel }}_F^2]\le (1-\frac{r}{n})\mathrm{\parallel }AB{\mathrm{\parallel }}_F^2$, per-entry variance $\mathrm{\parallel }AB{\mathrm{\parallel }}_F^2\mathrm{/}{n}^2$ and bias $\mathbb{E}[C]=\frac{r}{n}AB$. Alternatively, the algorithm can compute an unbiased estimation with expected total squared error $\frac{n}{r}\mathrm{\parallel }AB{\mathrm{\parallel }}_F^2$, recovering the state-of-art AMM error obtained by Pagh’s TensorSketch algorithm (Pagh, 2013). Our algorithm is a log-factor faster. The key insight in the algorithm is a new variation of pseudo-random rotation of the input matrices (a Fast Hadamard Transform with asymmetric diagonal scaling), which redistributes the Frobenius norm of the output $AB$ uniformly across its entries.