6
$\begingroup$

I need to compute the inverse of a matrix sum $A+D$, where the inverse of $A\in\mathbb{R}^{n\times n}$ is known. The matrix $D\in\mathbb{R}^{n\times n}$ is a diagonal matrix which can be thought of as a perturbation to $A$.

Assuming that $A+D$ is still full-rank, is there any efficient way to compute $(A+D)^{-1}$ using the known quantity $A^{-1}$?

$\endgroup$
  • 1
    $\begingroup$ Are the entries of $D$ relatively small? $\endgroup$ – JimmyK4542 Jul 27 '14 at 22:17
  • 1
    $\begingroup$ Duplicate with no upvoted or accepted answer is here: math.stackexchange.com/questions/792477/… $\endgroup$ – rajb245 Jul 27 '14 at 23:41
  • $\begingroup$ @rajb245 Thanks for the link. It seems that it cannot be done efficiently, in general. $\endgroup$ – Erik M Jul 28 '14 at 0:19
2
$\begingroup$

Continuing JimmyK4542's answer, we could write the following two relationships using the Woodbury Matrix identity:

$$(A+D)^{-1} = A^{-1}-A^{-1}(D^{-1}+A^{-1})^{-1}A^{-1}$$

$$ (D^{-1}+A^{-1})^{-1} = D - D(A+D)^{-1}D $$

In the second, we've treated $D^{-1}$ as large and $A^{-1}$ as the perturbation, which is sensical if $D$ was small to begin with. Plugging the second into the first, I get

$$(A+D)^{-1} = A^{-1}-A^{-1}(D - D(A+D)^{-1}D)A^{-1}$$

Expanding

$$(A+D)^{-1} = A^{-1}-A^{-1}DA^{-1} + A^{-1}D(A+D)^{-1}DA^{-1}$$

Now if $D$ is a small perturbation, we approximate $(A+D)^{-1}\approx A^{-1}$ on the right hand side only, and we get the approximation

$$(A+D)^{-1} \approx A^{-1}-A^{-1}DA^{-1} + A^{-1}DA^{-1}DA^{-1}$$

If we don't approximate, but use the first Woodward identity again, we get

$$ (A+D)^{-1} = A^{-1}-A^{-1}DA^{-1} + A^{-1}D(A^{-1}-A^{-1}(D^{-1}+A^{-1})^{-1}A^{-1})DA^{-1} $$

And expanding again

$$ (A+D)^{-1} = A^{-1}-A^{-1}DA^{-1} + A^{-1}DA^{-1}DA^{-1} -A^{-1}DA^{-1}(D^{-1}+A^{-1})^{-1}A^{-1}DA^{-1} $$

If $D$ is a small perturbation, we can approximate $(A^{-1}+D^{-1})^{-1}\approx D$ on the right hand side only, and we get the approximation

$$ (A+D)^{-1} \approx A^{-1}-A^{-1}DA^{-1} + A^{-1}DA^{-1}DA^{-1} -A^{-1}DA^{-1}DA^{-1}DA^{-1} $$

I claim continuing the procedure leads to an $N$th order approximation of

$$ (A+D)^{-1} \approx A^{-1}\sum_{n=0}^N (-1)^{n} (DA^{-1})^n, $$

which is the $N$th Taylor polynomial expansion of $(A+D)^{-1}$ about $D\approx \mathbf{0}$ (boldface zero means the zero matrix). Intuitively, the expression is convergent if $(DA^{-1})^n\rightarrow \mathbf{0}$ "fast enough" as $n\rightarrow\infty$. Non-rigorously thinking about this, I find that iterating powers of a matrix like this will make the entries get bigger and bigger if any eigenvalues of $(DA^{-1})$ are larger than $1$, giving a divergent summation. If all the eigenvalues of $(DA^{-1})$ are smaller than $1$, I would expect the terms in the sum to get smaller and smaller, contributing less and less to the result, and giving a convergent result. In this case I would expect the error to be bounded by term after the one you truncate, giving you an iterative way to know when to stop, e.g., calculate term by term and sum up until the contribution is less than $10^{-16}$ in all entries of the matrix (for double precision in a computer).

The ability for you to use the above technique then hinges on the eigenvalues of $(DA^{-1})$. I hope they are small enough!

$\endgroup$
2
$\begingroup$

The Woodbury Matrix Identity states that: $$(W+XYZ)^{-1} = W^{-1}-W^{-1}X(Y^{-1}+ZW^{-1}X)^{-1}ZW^{-1}$$

Setting $W = A$, $Y = D$, and $X = Z = I$, we get: $$(A+D)^{-1} = A^{-1}-A^{-1}(D^{-1}+A^{-1})^{-1}A^{-1}$$

EDIT: If the entries of $D$ are very small, we get the approximation: $$(A+D)^{-1} \approx A^{-1}-A^{-1}DA^{-1}$$

$\endgroup$
  • 2
    $\begingroup$ How can we find $(D^{-1}+A)^{-1}$? It would have the same complexity as $(A+D)^{-1}$. $\endgroup$ – Klaas van Aarsen Jul 27 '14 at 22:02
  • $\begingroup$ Thank you. One would still need to compute the inverse of $A+D^{-1}$, but I suppose there is no way around this? I had hoped there was something similar to the Sherman-Morrison formula for diagonal (rather than just rank-1) perturbations. $\endgroup$ – Erik M Jul 27 '14 at 22:03
  • $\begingroup$ Ahh right, I guess this isn't very helpful then. $\endgroup$ – JimmyK4542 Jul 27 '14 at 22:15
  • 1
    $\begingroup$ Iterating the Woodbury identity results in the Taylor series for $(A+D)^{-1}$ about $D\approx 0$. I think that expression is convergent if $A^{-1}D$ has an operator norm smaller than $1$. If $D$ is small in some sense, I think that all this requires is that $A$ has all eigenvalues larger than $1$, and then you can just truncate the Taylor series with a "large enough" cutoff to get the error you are looking for. $\endgroup$ – rajb245 Jul 27 '14 at 23:51
  • 1
    $\begingroup$ @ErikMiehling If only a few of the diagonal entries of $D$ are non-zero, say $k \ll n$ of them, there is a short cut. In the Woodbury matrix identity, the $X$ and $Z$ need not be square matrices. You can replace $X, Y, Z$ by suitable $n\times k$, $k \times k$ and $k \times n$ matrices. The matrix you need to take inverse, $Y^{-1} + ZW^{-1}X$, is a $k \times k$ instead of $n \times n$ matrix! $\endgroup$ – achille hui Jul 28 '14 at 17:07

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.