the above with , we obtain that $$\begin{aligned}
 {\hat{\kappa}}_{\tilde{L}} &\le \frac{\tr(P^{-1/2} (C + \lambda I ) P^{-1/2})}{\lambda_d(P^{-1/2} (C + \lambda I ) P^{-1/2})} \\
&\le  k\frac{\lambda_k+\lambda}{\lambda} + \sum_{i=k+1}^d \frac{\lambda_i+\lambda}{\lambda}  \\
&= \frac{k \lambda_k + \sum_{i>k} \lambda_i}{\lambda} + d ~. \qedhere\end{aligned}$$

Sketched conditioning {#sec:lowCond}
---------------------

An exact computation of the SVD of the matrix $\bar{X}$ takes $O(nd^2)$. Instead, we will use the Block Lanczos method in order to approximate the truncated SVD of $\bar{X}$. Specifically, given a parameter $k \in [d]$, we invoke the Block Lanczos method with the parameters $\bar{X},k$ and $\epsilon'=1/2$. Recall that the output has the form $\tilde{X}_k = {\tilde{U}}_k {\tilde{\Sigma}}_k {\tilde{V}}_k^\top= \sum_{i=1}^k {\tilde{\sigma}}_i{\tilde{u}}_i {\tilde{v}}_i^\top$. Analogously to the exact sketched preconditioner, we define our sketched preconditioner by $$\label{eq:condSketch}
P^{-1/2}  = \sum_{i=1}^k \frac{{\tilde{u}}_i {\tilde{u}}_i^\top}{\sqrt{{\tilde{\sigma}}_i^2+\lambda}}  + \frac{I-\sum_{i=1}^k  {\tilde{u}}_i {\tilde{u}}_i^\top}{\sqrt{{\tilde{\sigma}}_k^2+\lambda}} ~.$$

\[thm:sketchCond\] Let $k \in [d]$ be a parameter and assume that the regularization parameter, $\lambda$, is larger that $\lambda_d$. Using the sketched preconditioner defined in , up to a multiplicative constant, we obtain the bound on the average condition number with probability at least $9/10$.

The rest of this section is devoted to the proof of . We follow along the lines of the proof of . Up to a 