multiplicative constant, we derive the same upper and lower bounds on the eigenvalues of $P^{-1/2} (C+\lambda I)P^{-1/2}$.

From now on, we assume that the bounds in (where $\epsilon'=1/2$) hold. This assumption will be valid with probability of at least $9/10$. We next introduce some notation. We can rewrite $P^{-1/2}  = {\tilde{U}}({\tilde{\Sigma}}^2+\lambda I)^{-1/2} {\tilde{U}}^\top$ where ${\tilde{\Sigma}}$ is a diagonal $d \times d$ with ${\tilde{\Sigma}}_{i,i} = {\tilde{\sigma}}_i$ if $i \le k$ and ${\tilde{\Sigma}}_i = {\tilde{\sigma}}_k$ if $i>k$. and the columns of ${\tilde{U}}$ are a completion of ${\tilde{u}}_1,\ldots,{\tilde{u}}_k$ to an orthonormal basis. Recall that the SVD of $\bar{X}$ is denoted by $\bar{X} = \sum_{i=1}^d \sigma_i u_i v_i^\top = U \Sigma V^\top$.

**(Upper bound on the leading eigenvalue)** We have $$\lambda_1(P^{-1/2} (C+\lambda I)P^{-1/2})  \le 17~.$$

Since $\lambda_1(P^{-1/2} (C+\lambda I)P^{-1/2}) = \|P^{-1/2} (C+\lambda I)P^{-1/2}\| = \|P^{-1/2} C P^{-1/2} + \lambda P^{-1}\|$, using the triangle inequality we have that $$\lambda_1(P^{-1/2} (C+\lambda I)P^{-1/2}) ~\le~ \|P^{-1/2} C P^{-1/2}\| + \lambda \|P^{-1}\| ~.$$ By the definition of $P$ we have that $\|P^{-1}\| = \frac{1}{{\tilde{\sigma}}_k^2 + \lambda}$ and therefore the second summand on the right hand side of the above is at most $\frac{\lambda}{{\tilde{\sigma}}_k^2+\lambda} \le 1$. As to the first summand, recall that $C = \bar{X} \bar{X}^\top$ and therefore $\|P^{-1/2} 