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.
$\begingroup$
$\endgroup$
3
-
6$\begingroup$ What do you expect that you cannot trivially find by searching the web? $\endgroup$– Christian WalugaNov 6, 2018 at 18:07
-
$\begingroup$ Please edit the post with: what do you do not understand? So people may be can help you $\endgroup$– Mauro VanzettoNov 7, 2018 at 11:51
-
$\begingroup$ This question is more suited to math.stackexchange, there in the linear-algebra and numerical mathematics section. $\endgroup$– NoxNov 7, 2018 at 13:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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,
- You have a matrix $A$ and you already have a computed $A^{-1}$.
- 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$.
- 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.
- 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
answered Nov 6, 2018 at 18:17