Bounding norm of difference of inverse of two PSD matrices

Question

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?

Answer 1

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.