C P^{-1/2}\| = \|\bar{X}^\top P^{-1/2} \|^2$. We will show that $\|\bar{X}^\top P^{-1/2} \| \le 4$ which will imply that $\|P^{-1/2} C P^{-1/2}\| \le 16$. To do so, we first apply the triangle inequality, $$\begin{aligned}
&\|\bar{X}^\top P^{-1/2}\|  = \| ({\tilde{X}}_k + (\bar{X} - {\tilde{X}}_k))^\top P^{-1/2} \| \\
&\quad \le \| {\tilde{X}}_k^\top P^{-1/2} \| + \|(\bar{X} - {\tilde{X}}_k)^\top P^{-1/2} \| ~.\end{aligned}$$ Let us consider one term at the time. Recall that ${\tilde{X}}_k = {\tilde{U}}_k {\tilde{\Sigma}}_k {\tilde{V}}_k^\top$. Since ${\tilde{U}}_k^\top {\tilde{U}}\in \reals^{k,d}$ is a diagonal matrix with ones on the diagonal, and since the spectral norm is invariant to multiplication by unitary matrices, we obtain that $$\begin{aligned}
&\|{\tilde{X}}_k^\top P^{-1/2}\| = \|{\tilde{V}}_k {\tilde{\Sigma}}_k {\tilde{U}}_k^\top {\tilde{U}}({\tilde{\Sigma}}^2+\lambda I)^{-1/2} {\tilde{U}}^\top\| \\
&\quad = \|{\tilde{\Sigma}}_k {\tilde{U}}_k^\top {\tilde{U}}({\tilde{\Sigma}}^2+\lambda I)^{-1/2} \| \\
&\quad = \max_{i \in [k]} \frac{{\tilde{\sigma}}_i}{ \sqrt{{\tilde{\sigma}}_i^2+\lambda}} 
\le \max_{i \in [k]} \frac{{\tilde{\sigma}}_i}{{\tilde{\sigma}}_i+\sqrt{\lambda}} 
\le 1 ~.\end{aligned}$$ Next, by the submutiplicativity of the spectral norm, $$\|(\bar{X} - {\tilde{X}}_k)^\top P^{-1/2} \| \le \|\bar{X}-{\tilde{X}}_k\| \cdot \|P^{-1/2}\| ~.$$ implies that $\|\bar{X}-{\tilde{X}}_k\| \le \tfrac{3}{2} \sigma_k$ and $$\begin{aligned}
&\|P^{-1/2}\| = \frac{1}{ \sqrt{{\tilde{\sigma}}_k^2+\lambda}} 
\le \frac{1}{\sqrt{{\tilde{\sigma}}_k^2}} \le \frac{1}{ \sqrt{\sigma_k^2 - (1/2) \sigma_{k+1}^2}} \\
&\quad \le \frac{1}{ \sigma_{k} \sqrt{\tfrac{1}{2}} } = \frac{ \sqrt{2}}{ \sigma_k} 
<\frac{ 2}{\sigma_k}~.\end{aligned}$$ Hence, $\|\bar{X}-{\tilde{X}}_k\| \cdot \|P^{-1/2}\| \le 3$. Combining all of the above bounds concludes 