8

The Sherman-Morrison formula $$ (A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} $$ results in small errors in relation to the standard matrix inverse operation after each application, as shown here. From what I understand, the Sherman-Morrison identity is exact, so the error must come from numerical problems. But where exactly? Also, are there any theoretical bounds for this error? Some sources argue that the error is related to the matrix condition number, but wouldn't that affect the standard inversion too?

Christian Clason
  • 12,301
  • 3
  • 48
  • 68
rcpinto
  • 180
  • 4
  • 1
    Can you give a minimal reproducible example showing these errors? The pdf you link to applies the formula to a sequence of $N$ random updates $u_k,v_k$ and shows error $|A^{-1}{\mathrm{sm},k} - A^{-1}|$ as growing slower than something like $N\epsilon{\mathrm{mach}}$ ($\sqrt{N}\epsilon_{\mathrm{mach}}$?), which doesn't seem unreasonable to me. – Kirill Aug 06 '15 at 05:43
  • The example I have is the one you saw in the pdf. So would you say it is just a precision issue? So the error occurs in both approaches, but since we are measuring only the difference between them, it is not possible to tell? – rcpinto Aug 06 '15 at 05:53
  • The reason I'm asking this is because I applied this formula in a paper and one reviewer asked for the error bounds of using this instead of the direct approach. And as you can see, I'm lost. – rcpinto Aug 06 '15 at 05:55
  • 1
    If you perform $N$ operations and each has error $\pm\epsilon$, you accumulate on average an error of $\sqrt{N}\epsilon$ in a kind of random walk. It's just accumulation of roundoff errors, and not anything specifically to do with Sherman-Morrison, that's the non-exceptional behaviour you'd usually get. – Kirill Aug 06 '15 at 06:19
  • 2
    In Higham Accuracy and Stability of Numerical Algorithms (2002), Exercise 26.2 forward and backward error bounds for Sherman-Morrison (not running error after $N$ updates - which is it that you're after?) are listed as a research problem, with a citation to E. L. Yip in J. Sci. Statist. Comput. 7 (3) 1986, which I can't look up right now. Can you state the question more clearly please? – Kirill Aug 06 '15 at 06:29
  • Thank you very much, Kirill. It seems then that if the matrix is well conditioned, the formula is stable, which would be the same for standard inversion. IOW, there should be no differences in results, which was indeed what I have shown in my paper. The exact reviewer question was "are there any error bounds on the accuracy of matrix lambda calculated by the Sherman-Morrison formula, and how might these effect the estimation of the Mahalanobis distances in equation 22?" (he refers to the fact that I'm using an inverse covariance matrix estimated from S-M formula in a Mahalanobis distance comp) – rcpinto Aug 06 '15 at 16:46
  • 1
    Sherman-Morrison requires you to compute $A^{-1} v$. Note that $A + vv^T$ can be well-conditioned even when $A$ is not. – tmyklebu Aug 07 '15 at 01:34

0 Answers0