Before revision:  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 algorithm needs n=d ^{ \log ( r \kappa )  (\hat{\Pi} \hat{\Pi} -\Pi_*\|_F \leq O( 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_*.