- Source: Woodbury matrix identity
In mathematics, specifically linear algebra, the Woodbury matrix identity – named after Max A. Woodbury – says that the inverse of a rank-k correction of some matrix can be computed by doing a rank-k correction to the inverse of the original matrix. Alternative names for this formula are the matrix inversion lemma, Sherman–Morrison–Woodbury formula or just Woodbury formula. However, the identity appeared in several papers before the Woodbury report.
The Woodbury matrix identity is
(
A
+
U
C
V
)
−
1
=
A
−
1
−
A
−
1
U
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
,
{\displaystyle \left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1},}
where A, U, C and V are conformable matrices: A is n×n, C is k×k, U is n×k, and V is k×n. This can be derived using blockwise matrix inversion.
While the identity is primarily used on matrices, it holds in a general ring or in an Ab-category.
The Woodbury matrix identity allows cheap computation of inverses and solutions to linear equations. However, little is known about the numerical stability of the formula. There are no published results concerning its error bounds. Anecdotal evidence suggests that it may diverge even for seemingly benign examples (when both the original and modified matrices are well-conditioned).
Discussion
To prove this result, we will start by proving a simpler one. Replacing A and C with the identity matrix I, we obtain another identity which is a bit simpler:
(
I
+
U
V
)
−
1
=
I
−
U
(
I
+
V
U
)
−
1
V
.
{\displaystyle \left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.}
To recover the original equation from this reduced identity, replace
U
{\displaystyle U}
by
A
−
1
U
{\displaystyle A^{-1}U}
and
V
{\displaystyle V}
by
C
V
{\displaystyle CV}
.
This identity itself can be viewed as the combination of two simpler identities. We obtain the first identity from
I
=
(
I
+
P
)
−
1
(
I
+
P
)
=
(
I
+
P
)
−
1
+
(
I
+
P
)
−
1
P
,
{\displaystyle I=(I+P)^{-1}(I+P)=(I+P)^{-1}+(I+P)^{-1}P,}
thus,
(
I
+
P
)
−
1
=
I
−
(
I
+
P
)
−
1
P
,
{\displaystyle (I+P)^{-1}=I-(I+P)^{-1}P,}
and similarly
(
I
+
P
)
−
1
=
I
−
P
(
I
+
P
)
−
1
.
{\displaystyle (I+P)^{-1}=I-P(I+P)^{-1}.}
The second identity is the so-called push-through identity
(
I
+
U
V
)
−
1
U
=
U
(
I
+
V
U
)
−
1
{\displaystyle (I+UV)^{-1}U=U(I+VU)^{-1}}
that we obtain from
U
(
I
+
V
U
)
=
(
I
+
U
V
)
U
{\displaystyle U(I+VU)=(I+UV)U}
after multiplying by
(
I
+
V
U
)
−
1
{\displaystyle (I+VU)^{-1}}
on the right and by
(
I
+
U
V
)
−
1
{\displaystyle (I+UV)^{-1}}
on the left.
Putting all together,
(
I
+
U
V
)
−
1
=
I
−
U
V
(
I
+
U
V
)
−
1
=
I
−
U
(
I
+
V
U
)
−
1
V
.
{\displaystyle \left(I+UV\right)^{-1}=I-UV\left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-1}V.}
where the first and second equality come from the first and second identity, respectively.
= Special cases
=When
V
,
U
{\displaystyle V,U}
are vectors, the identity reduces to the Sherman–Morrison formula.
In the scalar case, the reduced version is simply
1
1
+
u
v
=
1
−
u
v
1
+
v
u
.
{\displaystyle {\frac {1}{1+uv}}=1-{\frac {uv}{1+vu}}.}
Inverse of a sum
If n = k and U = V = In is the identity matrix, then
(
A
+
B
)
−
1
=
A
−
1
−
A
−
1
(
B
−
1
+
A
−
1
)
−
1
A
−
1
=
A
−
1
−
A
−
1
(
A
B
−
1
+
I
)
−
1
.
{\displaystyle {\begin{aligned}\left(A+B\right)^{-1}&=A^{-1}-A^{-1}\left(B^{-1}+A^{-1}\right)^{-1}A^{-1}\\[1ex]&=A^{-1}-A^{-1}\left(AB^{-1}+{I}\right)^{-1}.\end{aligned}}}
Continuing with the merging of the terms of the far right-hand side of the above equation results in Hua's identity
(
A
+
B
)
−
1
=
A
−
1
−
(
A
+
A
B
−
1
A
)
−
1
.
{\displaystyle \left({A}+{B}\right)^{-1}={A}^{-1}-\left({A}+{A}{B}^{-1}{A}\right)^{-1}.}
Another useful form of the same identity is
(
A
−
B
)
−
1
=
A
−
1
+
A
−
1
B
(
A
−
B
)
−
1
,
{\displaystyle \left({A}-{B}\right)^{-1}={A}^{-1}+{A}^{-1}{B}\left({A}-{B}\right)^{-1},}
which, unlike those above, is valid even if
B
{\displaystyle B}
is singular, and has a recursive structure that yields
(
A
−
B
)
−
1
=
∑
k
=
0
∞
(
A
−
1
B
)
k
A
−
1
{\displaystyle \left({A}-{B}\right)^{-1}=\sum _{k=0}^{\infty }\left({A}^{-1}{B}\right)^{k}{A}^{-1}}
if the spectral radius of
A
−
1
B
{\displaystyle A^{-1}B}
is less than one. That is, if the above sum converges then it is equal to
(
A
−
B
)
−
1
{\displaystyle (A-B)^{-1}}
.
This form can be used in perturbative expansions where B is a perturbation of A.
= Variations
=Binomial inverse theorem
If A, B, U, V are matrices of sizes n×n, k×k, n×k, k×n, respectively, then
(
A
+
U
B
V
)
−
1
=
A
−
1
−
A
−
1
U
B
(
B
+
B
V
A
−
1
U
B
)
−
1
B
V
A
−
1
{\displaystyle \left(A+UBV\right)^{-1}=A^{-1}-A^{-1}UB\left(B+BVA^{-1}UB\right)^{-1}BVA^{-1}}
provided A and B + BVA−1UB are nonsingular. Nonsingularity of the latter requires that B−1 exist since it equals B(I + VA−1UB) and the rank of the latter cannot exceed the rank of B.
Since B is invertible, the two B terms flanking the parenthetical quantity inverse in the right-hand side can be replaced with (B−1)−1, which results in the original Woodbury identity.
A variation for when B is singular and possibly even non-square:
(
A
+
U
B
V
)
−
1
=
A
−
1
−
A
−
1
U
(
I
+
B
V
A
−
1
U
)
−
1
B
V
A
−
1
.
{\displaystyle (A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}.}
Formulas also exist for certain cases in which A is singular.
Pseudoinverse with positive semidefinite matrices
In general Woodbury's identity is not valid if one or more inverses are replaced by (Moore–Penrose) pseudoinverses. However, if
A
{\displaystyle A}
and
C
{\displaystyle C}
are positive semidefinite, and
V
=
U
H
{\displaystyle V=U^{\mathrm {H} }}
(implying that
A
+
U
C
V
{\displaystyle A+UCV}
is itself positive semidefinite), then the following formula provides a generalization:
(
X
X
H
+
Y
Y
H
)
+
=
(
Z
Z
H
)
+
+
(
I
−
Y
Z
+
)
H
X
+
H
E
X
+
(
I
−
Y
Z
+
)
,
Z
=
(
I
−
X
X
+
)
Y
,
E
=
I
−
X
+
Y
(
I
−
Z
+
Z
)
F
−
1
(
X
+
Y
)
H
,
F
=
I
+
(
I
−
Z
+
Z
)
Y
H
(
X
X
H
)
+
Y
(
I
−
Z
+
Z
)
,
{\displaystyle {\begin{aligned}\left(XX^{\mathrm {H} }+YY^{\mathrm {H} }\right)^{+}&=\left(ZZ^{\mathrm {H} }\right)^{+}+\left(I-YZ^{+}\right)^{\mathrm {H} }X^{+\mathrm {H} }EX^{+}\left(I-YZ^{+}\right),\\Z&=\left(I-XX^{+}\right)Y,\\E&=I-X^{+}Y\left(I-Z^{+}Z\right)F^{-1}\left(X^{+}Y\right)^{\mathrm {H} },\\F&=I+\left(I-Z^{+}Z\right)Y^{\mathrm {H} }\left(XX^{\mathrm {H} }\right)^{+}Y\left(I-Z^{+}Z\right),\end{aligned}}}
where
A
+
U
C
U
H
{\displaystyle A+UCU^{\mathrm {H} }}
can be written as
X
X
H
+
Y
Y
H
{\displaystyle XX^{\mathrm {H} }+YY^{\mathrm {H} }}
because any positive semidefinite matrix is equal to
M
M
H
{\displaystyle MM^{\mathrm {H} }}
for some
M
{\displaystyle M}
.
Derivations
= Direct proof
=The formula can be proven by checking that
(
A
+
U
C
V
)
{\displaystyle (A+UCV)}
times its alleged inverse on the right side of the Woodbury identity gives the identity matrix:
(
A
+
U
C
V
)
[
A
−
1
−
A
−
1
U
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
]
=
{
I
−
U
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
}
+
{
U
C
V
A
−
1
−
U
C
V
A
−
1
U
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
}
=
{
I
+
U
C
V
A
−
1
}
−
{
U
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
+
U
C
V
A
−
1
U
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
}
=
I
+
U
C
V
A
−
1
−
(
U
+
U
C
V
A
−
1
U
)
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
=
I
+
U
C
V
A
−
1
−
U
C
(
C
−
1
+
V
A
−
1
U
)
(
C
−
1
+
V
A
−
1
U
)
−
1
V
A
−
1
=
I
+
U
C
V
A
−
1
−
U
C
V
A
−
1
=
I
.
{\displaystyle {\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{I-U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}+UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&I+UCVA^{-1}-\left(U+UCVA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left(C^{-1}+VA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}}
= Alternative proofs
=Applications
This identity is useful in certain numerical computations where A−1 has already been computed and it is desired to compute (A + UCV)−1. With the inverse of A available, it is only necessary to find the inverse of C−1 + VA−1U in order to obtain the result using the right-hand side of the identity. If C has a much smaller dimension than A, this is more efficient than inverting A + UCV directly. A common case is finding the inverse of a low-rank update A + UCV of A (where U only has a few columns and V only a few rows), or finding an approximation of the inverse of the matrix A + B where the matrix B can be approximated by a low-rank matrix UCV, for example using the singular value decomposition.
This is applied, e.g., in the Kalman filter and recursive least squares methods, to replace the parametric solution, requiring inversion of a state vector sized matrix, with a condition equations based solution. In case of the Kalman filter this matrix has the dimensions of the vector of observations, i.e., as small as 1 in case only one new observation is processed at a time. This significantly speeds up the often real time calculations of the filter.
In the case when C is the identity matrix I, the matrix
I
+
V
A
−
1
U
{\displaystyle I+VA^{-1}U}
is known in numerical linear algebra and numerical partial differential equations as the capacitance matrix.
See also
Sherman–Morrison formula
Schur complement
Matrix determinant lemma, formula for a rank-k update to a determinant
Invertible matrix
Moore–Penrose pseudoinverse § Updating the pseudoinverse
Notes
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.7.3. Woodbury Formula", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
External links
Some matrix identities
Weisstein, Eric W. "Woodbury formula". MathWorld.
Kata Kunci Pencarian:
- Woodbury matrix identity
- Sherman–Morrison formula
- List of mathematical identities
- Max A. Woodbury
- Weinstein–Aronszajn identity
- Invertible matrix
- Schur complement
- Woodbury
- Outline of linear algebra
- Low-rank matrix approximations
