[Math] L2 norm of an inverse of a sum of matrices

inverselinear algebramatricesnormed-spaces

I am trying to take the L2 norm of the following expression: $-(H^{-1} + bI)^{-1}v$, where $H$ is a psd matrix, b is a scalar, and $v$ is a vector. In particular I am having trouble with the first factor: $-(H^{-1} + bI)^{-1}$ where I have an inverse of a sum of matrices.

To give more context, I found this in a paper that I am trying to understand, and what we would end up getting is that the norm lies between $(1/s_{max}(H) + b)^{-1}||v||_2$ and $(1/s_{min}(H) + b)^{-1}||v||_2$, where $s_{max}$ and $s_{min}$ are the max and the min singular values of H. I understand that the singular values come from taking the L2 norm of $H^{-1}$, but I do not understand how to propagate it to the inverse sum of the two matrices. Any help would be greatly appreciated.

Best Answer

Help: You need multiple concepts to prove this. I suppose your $H$ is symmetric Positive definite (since, it has inverse in your expression). Now try to prove the following

  • If singular values of $H$ are $\sigma_1,\dots,\sigma_N$, then the singular values of $H^{-1}$ are $\sigma_1^{-1},\dots,\sigma_N^{-1}$
  • Singular values of $(H^{-1}+bI)$ are $b+\sigma_1^{-1},\dots,b+\sigma_N^{-1}$
  • what are the singular values of $(H^{-1}+bI)^{-1}$ using previous two ideas.
  • For any matrix $A$ and vector $v$, the following holds $||Av||_2 \leq ||A||_2||v||_2$ where $||A||_2$ is the induced $L2$ norm. See how this is related to Cauchy-Schwarz inequality
  • Try to prove $||A||_2 = \sigma_1$ where $\sigma_1$ is the largest singular value of $A$ and $||A^{-1}||_2 = \sigma_N^{-1}$ where $\sigma_N$ is the smallest singular value of $A$

Now combining all these, try to see if your problem can be solved.

UPDATE: The OP asked for help on Lowerbound, I am not sure if this approach is correct. Please try to verify. Note that for any $v$, the following holds (try to see why this holds yourself) \begin{align} \sigma_N = \min_{x}||Ax||_2 ~,~s.t.~~||x||_2=1 \end{align} Thus, for a given vector $v$, define $c=||v||_2$, we have \begin{align} c\sigma_N = \min_{||x||=c}||Ax||_2 \leq ||Av||_2 \end{align} The second part comes from the fact that for a given function $f(x)$, $$\min_x~f(x)\leq f(v)~,~~x,v\in\mathbb{R}$$ Now, try to see if you can use $A=(H^{-1}+bI)^{-1}$. Also, think what is $\sigma_N(A)$ in this case.

Related Question