first a preconditioner that is based on an exact rank-$k$ approximation of the data matrix. Let $X \in \reals^{d \times n}$ be the matrix whose $i$-th columns is $x_i$ and let $\bar{X}=n^{-1/2} X$. Denote by $\bar{X}= \sum_{i=1}^{\textrm{rank}(\bar{X})} \sigma_i u_i v_i^\top = U \Sigma V^\top$ the SVD of $\bar{X}$ and recall that $\bar{X}_k= \sum_{i=1}^k \sigma_i u_i v_i^\top$ is the best $k$-rank approximation of $\bar{X}$. Note that $\bar{X}\bar{X}^\top=C$ and therefore $\sigma_i^2 = \lambda_i(C)=\lambda_i$. Furthermore, the left singular vectors of $\bar{X}$, $u_1,\ldots,u_k$, coincide with the $k$ leading eigenvectors of the matrix $C$. Consider the preconditioner, $$P^{-1/2}  = \sum_{i=1}^k \frac{u_i u_i^\top}{\sqrt{\lambda_i+\lambda}} + \frac{I-\sum_{i=1}^k  u_i u_i^\top}{\sqrt{\lambda_k+\lambda}}~,$$ where $u_{k+1},\ldots, u_d$ are obtained from a completion of $u_1,\ldots,u_k$ to an orthonormal basis.

\[lem:exactCondSketch\] Let $k \in [d]$ be a parameter and assume that the regularization parameter, $\lambda$, is larger than $\lambda_d$. Using the exact sketched preconditioner, we obtain $$\label{eq:exactCondSketchCond}
{\hat{\kappa}}_{\tilde{L}} \le \frac{k \lambda_k+ \sum_{i>k} \lambda_i}{\lambda} + d ~.$$

A simple calculation shows that for $i=1,\ldots,k$, $$\lambda_{i} (P^{-1/2} (C + \lambda I ) P^{-1/2} )  = \frac{\lambda_i+\lambda}{\lambda_i+\lambda} = 1 ~.$$ Similarly, for $i=k+1,\ldots, d$, $$\lambda_{i} (P^{-1/2} (C + \lambda I ) P^{-1/2} ) = \frac{\lambda_i+\lambda}{\lambda_k+\lambda} ~.$$ Finally, $$\lambda_{d} (P^{-1/2} (C + \lambda I ) P^{-1/2}) \ge \frac{\lambda}{\lambda_k+\lambda}~.$$ Combining 