Furthermore, following the interpretation of our main result in , we note that for a “runtime budget” of $\tilde{O}(ndk)$, we can set the regularization parameter of CG to be of order $\lambda_k/k^2$ (which is usually much greater than the RHS of ).

#### Linear Sketching: 

Several recently developed methods in numerical linear algebra are based on the so-called *sketch-and-solve* approach, which essentially suggests that given a matrix $A$, we first replace it with a smaller random matrix $AS$, and then perform the computation on $AS$ [@woodruff2014sketching; @clarkson2013low; @sarlos2006improved]. For example, it is known that if the entries of $S$ are i.i.d. standard normal variables and $S$ has $p=\Omega(k/\epsilon)$ columns, then with high probability, the column space of $AS$ contains a $(1+\epsilon)$ rank-$k$ approximation to $A$ with respect to the Frobenius norm. This immediately yields a fast PCA algorithm (see Section 4.1 in [@woodruff2014sketching]).

While the above sketch-and-solve approach sounds promising for this purpose, our analysis reveals that controlling the Frobenius norm error does not suffice for our needs. We need spectral norm bounds, which are known to be more challenging [@witten2013randomized]. Furthermore, as mentioned above, the success of our conditioning method heavily depends on the stronger per vector error guarantees 