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.
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