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.

  • $\begingroup$ what is the "trouble"? $\endgroup$ – dineshdileep Aug 5 '15 at 5:57
  • $\begingroup$ I just edited the question, hopefully that gives more context. My apologies. $\endgroup$ – Pedrito Aug 5 '15 at 13:48

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.

  • $\begingroup$ Thank you so much, this is very helpful! I managed to show the points you made, and using the inequality you provided (similar to Cauchy-Schwartz) I get the upper bound. I am still having trouble with the lower bound though. $\endgroup$ – Pedrito Aug 7 '15 at 18:52
  • $\begingroup$ Thank you very much for your edited response, that worked out! $\endgroup$ – Pedrito Aug 13 '15 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.