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