Before revision:  The running time of both these algorithms, however, is d^{\Omega(1/\alpha^4)} and the error bounds on } \|\Pi-\Pi_*\|_F ^2 = \kappa^4 \log (r ) (\emph{  1/ \alpha^2), where hides polylogarithmic factors in 1/ \alpha . Here, \Pi_* is the projection matrix to the range space of \Sigma_*. The algorithm needs n=d ^{ \log ( r \kappa )  (\hat{\Pi} \hat{\Pi}  1/ \alpha^2) samples and runs in time n^{\log (r \kappa) \tilde{O(1/\alpha^4)} time where \kappa is the ratio of the largest to smallest non-zero eigenvalues of \Sigma_*.
After revision:  The running time of both these algorithms, however, is d^{\Omega(1/\alpha^4)} and the error bounds on } \|\Pi-\Pi_*\|_F ^2 = \kappa^4 \log (r ) (\emph{ 1/ \alpha^2), where hides polylogarithmic factors in 1/ \alpha ) d ^{ \log ( r \kappa )  (\hat{\Pi} \hat{\Pi} 1/ \alpha^2) samples and runs in time n^{\log (r \kappa) \tilde{O(1/\alpha^4)} time where \kappa is the ratio of the largest to smallest non-zero eigenvalues of \Sigma_*.