our proof.

**(Refined upper bound on the last $d-k$ eigenvalues)** For any $i \in \{k+1,\ldots,d\}$, $$\lambda_i \left(P^{-1/2} (C+ \lambda I)P^{-1/2} \right) \le \frac{2 (\lambda_i+\lambda)}{\lambda_k+\lambda}~.$$

Using the Courant minimax principle [@bhatia2013matrix], we obtain the following bound for all $i \in \{k+1,\ldots,d\}$: $$\begin{aligned}
&\lambda_i \left(P^{-1/2} (C+ \lambda I ) P^{-1/2} \right) \\
&= \max_{\substack{\mathcal{M} \subseteq \reals^d:\\ \dim(\mathcal{M}) =i}}\min_{\substack{x \in \cM:\\x \neq 0}} \frac{  x^\top P^{-1/2} (C+\lambda I) P^{-1/2} x}{\|x\|^2} \\
& = \max_{\substack{\mathcal{M} \subseteq \reals^d:\\ \dim(\mathcal{M}) =i}}\min_{\substack{x \in \cM:\\ x \neq 0}} \frac{  x^\top P^{-1/2} (C+\lambda I) P^{-1/2} x}{\|P^{-1/2}x\|^2} \cdot \frac{\|P^{-1/2}x\|^2} {\|x\|^2} \\
& \le \left(\max_{\substack{\mathcal{M} \subseteq \reals^d:\\ \dim(\mathcal{M}) =i}}\min_{\substack{x \in \cM: \\x \neq 0}} \frac{  x^\top P^{-1/2} (C+\lambda I) P^{-1/2} x}{\|P^{-1/2}x\|^2}\right) \times\\
& \qquad \left( \max_{\substack{x \in \reals^d:\\ x \neq 0}} \frac{x^\top P^{-1} x}{\|x\|^2} \right)\\
&= \lambda_i \left(C+\lambda  I \right) \cdot \lambda_1(P^{-1})  = (\lambda_i+\lambda) \cdot (\tilde{\sigma}_k^2+\lambda)^{-1} ~.
$$ Finally, using we have that ${\tilde{\sigma}}_k^2 \ge \sigma_k^2 - \frac{1}{2} \sigma_{k+1}^2 \ge \tfrac{1}{2} \sigma_k^2 = \tfrac{1}{2} \lambda_k$ and therefore, $$(\tilde{\sigma}_k^2+\lambda)^{-1} ~\le~ (\tfrac{1}{2} \lambda_k +\lambda)^{-1} ~\le~ 2\, (\lambda_k+\lambda)^{-1} ~. \qedhere$$

\[lem:lowerSmall\] **(Lower bound on the smallest eigenvalue)** $$\lambda_d( P^{-1/2} C P^{-1/2}) \ge \frac{\lambda}{19 (\lambda_k+\lambda)}~.$$

Note that $$\label{eq:digging0}
\lambda_d (P^{-1/2} (C+\lambda I) P^{-1/2}) = \frac{1}{\|P^{1/2} (C+\lambda I)^{-1} P^{1/2}\|}~,$$ so we can derive an upper bound 