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