@report {1616780,
	title = {Errata: Analysis of a randomized approximation scheme for matrix multiplication},
	year = {2012},
	institution = {ArXiv Report},
	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{\textquoteright}s inequality and a tail inequality for quadratic forms in subgaussian random vectors.



	Errata



	\&nbsp;


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


	\&nbsp;

},
	url = {http://arxiv.org/abs/1211.5414},
	author = {Daniel Hsu and Sham M. Kakade and Zhang, Tong}
}
