on $\|P^{1/2} (C+\lambda I)^{-1} P^{1/2}\|$. Consider an arbitrary completion of $\tilde{v}_1,\ldots,\tilde{v}_k$ to an orthonormal set, $\tilde{v}_1,\ldots,\tilde{v}_d \in \reals^n$. Let $\tilde{V} \in \reals^{n \times d}$ be the matrix whose $i$-th column is ${\tilde{v}}_i$. Since the spectral norm is unitary invariant and both ${\tilde{U}}$ and ${\tilde{V}}$ have orthonormal columns, $$\begin{aligned}
 &\|P^{1/2} (C+\lambda I)^{-1} P^{1/2}\| \notag\\
&= \|{\tilde{U}}({\tilde{\Sigma}}^2+\lambda I)^{1/2} {\tilde{U}}^\top (C+\lambda I)^{-1} {\tilde{U}}({\tilde{\Sigma}}^2+\lambda I)^{1/2} {\tilde{U}}^\top\| \notag \\
&= \|{\tilde{V}}({\tilde{\Sigma}}^2+\lambda I)^{1/2} {\tilde{U}}^\top (C+\lambda I)^{-1} {\tilde{U}}({\tilde{\Sigma}}^2+\lambda I)^{1/2} {\tilde{V}}^\top\| ~.\end{aligned}$$ Denote by ${\tilde{Z}}= {\tilde{U}}({\tilde{\Sigma}}^2+\lambda I)^{1/2} {\tilde{V}}^\top$. By the triangle inequality and the submutiplicativity of the spectral norm, $$\begin{aligned}
&\|{\tilde{Z}}^\top(C+\lambda I)^{-1} {\tilde{Z}}\| \le \|\bar{X}^\top (C+\lambda I)^{-1} \bar{X}\| \notag\\
&\qquad + \|({\tilde{Z}}-\bar{X})^\top (C+\lambda I)^{-1} ({\tilde{Z}}-\bar{X})\| \notag \\
& \le \|\bar{X}^\top (C+\lambda I)^{-1} \bar{X}\|+  \|{\tilde{Z}}-\bar{X}\|^2 \|(C+\lambda I)^{-1}\|~. \label{eq:digging15}\end{aligned}$$ To bound the first summand of , we use the unitary invariance to obtain $$\begin{aligned}
 &\|\bar{X}^\top (C+\lambda I)^{-1} \bar{X} \| = \|V \Sigma U^\top U (\Sigma^2 +\lambda I)^{-1} U^\top U \Sigma V^\top\| \notag\\
&\quad = \|\Sigma  (\Sigma^2 +\lambda I)^{-1} \Sigma \| = \max_i \frac{\lambda_i^2}{\lambda_i^2+\lambda} \le 1~.\end{aligned}$$ For the second summand of , note that $\|(C+ \lambda I)^{-1}\|= \frac{1}{\lambda_d+\lambda}$ and that, using the triangle inequality, $$\begin{aligned}
&\|{\tilde{Z}}- \bar{X}\| = \|({\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top - \bar{X}) + ({\tilde{Z}}-  {\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top) \|\\
&\quad \le \|{\tilde{U}}{\tilde{\Sigma}}{\tilde{V}}^\top - \bar{X}\| + 