Errata: Analysis of a randomized approximation scheme for matrix multiplication

Abstract:

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.

Errata

 

The analysis in Example 4.3 is flawed due to an incorrect bound on

  \|E[X_j^2]\|_2 .

It is possible to fix by introducing a factor of

  max_i { \|a_i\|_2 / \|b_i\|_2 , \|b_i\|_2 / \|a_i\|_2 }

in the bound, which ultimately leads to a significantly worse result.

(Note: There is no problem if A = B.)

Thanks to Joel Tropp for pointing out this bug.

A slightly different algorithm avoids this issue and leads to the same running time bound; see

  http://arxiv.org/abs/1211.5414

for details.

DH 2012-11-25

---

A slightly different sampling scheme also fixes the problem; see

  http://arxiv.org/abs/1410.4429

for details.

DH 2014-10-17

 

Publisher's Version

See also: 2012
Last updated on 10/11/2021