Bounding norm of difference of inverse of two PSD matrices I am going through this paper (https://arxiv.org/pdf/1902.07826.pdf) and I am stuck at the proof of Lemma 7 (on page 22).
The goal is to prove that for any two PSD matrices $M, N$ of same dimensions, we have $||N(I + MN)^{-1}|| \leq ||N||$. The proof is given as follows: For ease, let us assume that $M, N$ are invertible matrices. We can simplify $N(I + MN)^{-1} = NN^{-1}(N^{-1} + M)^{-1} = (N^{-1} + M)^{-1} \preccurlyeq N$.
I follow all the steps except the last step, i.e. $(N^{-1} + M)^{-1} \preccurlyeq N$. How is this true?
Further, I would like to bound the following expression where $M, N_1, N_2$ are PSD invertible matrices
$$ ||N_1(I + MN_1)^{-1} - N_2(I + MN_2)^{-1}|| $$
A naive way to bound it is to simply use $||a - b|| \leq ||a|| + ||b||$ and bound it as $||N_1(I + MN_1)^{-1} - N_2(I + MN_2)^{-1}|| \leq ||N_1|| + ||N_2||$ using the above lemma.
I have a hunch that it can be upper bounded by $||N_1 - N_2||$ which is tighter, but I cannot prove it. Any ideas on how we can bound it?
 A: For your first question, in general if $A\succeq B\succ0$, then $B^{-1/2}AB^{-1/2}\succeq I$. Hence $B^{1/2}A^{-1}B^{1/2}=(B^{-1/2}AB^{-1/2})^{-1}\preceq I$ and $A^{-1}\preceq B^{-1}$.
In your case, when $N\succ0$ and $M\succeq0$, we have $A=(N^{-1}+M)\succeq B=N^{-1}$. It follows that $A^{-1}=(N^{-1}+M)^{-1}\preceq B^{-1}=N$ and we obtain $\|N(I+MN)^{-1}\|\le\|N\|$. By a continuity argument, the inequality also holds when $N$ is only positive semidefinite.
For your second question, we have
\begin{aligned}
&N_1(I+MN_1)^{-1}-N_2(I+MN_2)^{-1}\\
&=\left[N_1(I+MN_1)^{-1}-N_1(I+MN_2)^{-1}\right]
+\left[N_1(I+MN_2)^{-1}-N_2(I+MN_2)^{-1}\right]\\
&=N_1(I+MN_1)^{-1}\left[(I+MN_2)-(I+MN_1)\right](I+MN_2)^{-1}
+(N_1-N_2)(I+MN_2)^{-1}\\
&=N_1(I+MN_1)^{-1}M(N_2-N_1)(I+MN_2)^{-1}
+(N_1-N_2)(I+MN_2)^{-1}\\
&=\left[I-N_1(I+MN_1)^{-1}M\right](N_1-N_2)(I+MN_2)^{-1}\\
&=(I+N_1M)^{-1}(N_1-N_2)(I+MN_2)^{-1},\\
\end{aligned}
where we have used the identity $(I+UV)^{-1}=I-U(I+VU)^{-1}V$ on last line. It follows that
\begin{aligned}
&\|N_1(I+MN_1)^{-1}-N_2(I+MN_2)^{-1}\|\\
\le\,&\|(I+N_1M)^{-1}\|\|N_1-N_2\|\|(I+MN_2)^{-1}\|\\
=\,&\left\|\left[(I+N_1M)^{-1}\right]^\ast\right\|\|N_1-N_2\|\|(I+MN_2)^{-1}\|\\
=\,&\|(I+MN_1)^{-1}\|\|N_1-N_2\|\|(I+MN_2)^{-1}\|.
\end{aligned}
Unfortunately, $\|(I+MN_1)^{-1}\|$ or $\|(I+MN_1)^{-1}\|$ are not bounded above by any constant. To illustrate, let $t>0$,
$$
M=\pmatrix{1&0\\ 0&t^2} \text{ and }\ N_1=\pmatrix{1&1/t\\ 1/t&1/t^2}.
$$
Then
$$
(I+MN_1)^{-1}=\pmatrix{2&1/t\\ t&2}^{-1}=\frac13\pmatrix{2&-1/t\\ -t&2},
$$
whose norm is unbounded above because the norm of its second column is unbounded above.
