-4
$\begingroup$

Can someone please explain what is the Sherman-Morrison formula and it's specialities when it comes to matrix calculations? I'm a little bit confused on understanding how the preconditioning works with Sherman-Morrison formula.

$\endgroup$
  • 6
    $\begingroup$ What do you expect that you cannot trivially find by searching the web? $\endgroup$ – Christian Waluga Nov 6 '18 at 18:07
  • $\begingroup$ Please edit the post with: what do you do not understand? So people may be can help you $\endgroup$ – Mauro Vanzetto Nov 7 '18 at 11:51
  • $\begingroup$ This question is more suited to math.stackexchange, there in the linear-algebra and numerical mathematics section. $\endgroup$ – Nox Nov 7 '18 at 13:25
2
$\begingroup$

Sherman-Morrison formula helps to find the inverse of the matrix cheap after a rank-1 update. Sherman-Morrison-Woodbury does it for a low-rank update (not necessarily rank-1).

In short,

  1. You have a matrix $A$ and you already have a computed $A^{-1}$.
  2. For some reason, you need to do a rank-1 update to $A$. This rank-1 update can be described as an outer-product of two vectors $u$ and $v$.
  3. So, you want an inverse of $(A+uv^T)$, but you don't want to redo all the calculations. Can you reuse your knowledge of $A^{-1}$? Yes.
  4. Sherman-Morrison tells you that $$ (A+uv^T)^{-1} = A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^tA^{-1}u} $$ which allows huge savings since you are just performing relatively cheap manipulations with an already obtained $A^{-1}$.

I strongly encourage you to read at least the Wikipedia articles regarding this topic in order to get an understanding about

  • numerical stability
  • requirements for the formula to be applicable

Important notes:

  • calculations of the inverse should be avoided at all costs
  • same ideas (SM, SMW) usually can be applied to factorizations, where they are extremely useful
$\endgroup$

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.