Woodbury matrix identity

src: slideplayer.com

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

${\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 all denote matrices of the correct (conformable) sizes. Specifically, A is n-by-n, U is n-by-k, C is k-by-k and V is k-by-n. This can be derived using blockwise matrix inversion.

For a more general formula for which the matrix C need not be invertible or even square, see Binomial inverse theorem.

In the special case where C is the 1-by-1 unit matrix, this identity reduces to the Sherman-Morrison formula. In the special case when C is the identity matrix I, the matrix ${\displaystyle I+VA^{-1}U}$ is known in numerical linear algebra and numerical partial differential equations as the capacitance matrix. For mere numbers, the identity reduces to the following relation of fractions

${\displaystyle {\frac {1}{a+x}}={\frac {1}{a}}-\left({\frac {1}{a}}\right)^{2}{\frac {1}{{\tfrac {1}{x}}+{\tfrac {1}{a}}}}.}$

Video Woodbury matrix identity

Direct proof

The formula can be proven by checking that ${\displaystyle (A+UCV)}$ times its alleged inverse on the right side of the Woodbury identity gives the identity matrix:

${\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}}}$

Maps Woodbury matrix identity

Algebraic proof

First consider these useful identities,

${\displaystyle {\begin{aligned}U+UCVA^{-1}U&=UC\left(C^{-1}+VA^{-1}U\right)=\left(A+UCV\right)A^{-1}U\\\left(A+UCV\right)^{-1}UC&=A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}\end{aligned}}}$

Now,

${\displaystyle {\begin{aligned}A^{-1}&=\left(A+UCV\right)^{-1}\left(A+UCV\right)A^{-1}\\&=\left(A+UCV\right)^{-1}\left(I+UCVA^{-1}\right)\\&=\left(A+UCV\right)^{-1}+\left(A+UCV\right)^{-1}UCVA^{-1}\\&=\left(A+UCV\right)^{-1}+A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}.\end{aligned}}}$

src: slideplayer.com

Derivation via blockwise elimination

Deriving the Woodbury matrix identity is easily done by solving the following block matrix inversion problem

${\displaystyle {\begin{bmatrix}A&U\\V&-C^{-1}\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}I\\0\end{bmatrix}}.}$

Expanding, we can see that the above reduces to

${\displaystyle {\begin{cases}AX+UY=I\\VX-C^{-1}Y=0\end{cases}}}$

which is equivalent to ${\displaystyle (A+UCV)X=I}$. Eliminating the first equation, we find that ${\displaystyle X=A^{-1}(I-UY)}$, which can be substituted into the second to find ${\displaystyle VA^{-1}(I-UY)=C^{-1}Y}$. Expanding and rearranging, we have ${\displaystyle VA^{-1}=(C^{-1}+VA^{-1}U)Y}$, or ${\displaystyle (C^{-1}+VA^{-1}U)^{-1}VA^{-1}=Y}$. Finally, we substitute into our ${\displaystyle AX+UY=I}$, and we have ${\displaystyle AX+U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}=I}$. Thus,

${\displaystyle (A+UCV)^{-1}=X=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}.}$

We have derived the Woodbury matrix identity.

src: www.pnas.org

Derivation from LDU decomposition

We start by the matrix

${\displaystyle {\begin{bmatrix}A&U\\V&C\end{bmatrix}}}$

By eliminating the entry under the A (given that A is invertible) we get

${\displaystyle {\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}A&U\\0&C-VA^{-1}U\end{bmatrix}}}$

Likewise, eliminating the entry above C gives

${\displaystyle {\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\V&C-VA^{-1}U\end{bmatrix}}}$

Now combining the above two, we get

${\displaystyle {\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}}$

Moving to the right side gives

${\displaystyle {\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}{\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}}$

which is the LDU decomposition of the block matrix into an upper triangular, diagonal, and lower triangular matrices.

Now inverting both sides gives

${\displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}^{-1}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}^{-1}{\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}{\begin{bmatrix}A^{-1}&0\\0&(C-VA^{-1}U)^{-1}\end{bmatrix}}{\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}A^{-1}+A^{-1}U(C-VA^{-1}U)^{-1}VA^{-1}&-A^{-1}U(C-VA^{-1}U)^{-1}\\-(C-VA^{-1}U)^{-1}VA^{-1}&(C-VA^{-1}U)^{-1}\end{bmatrix}}\qquad \mathrm {(1)} \end{aligned}}}$

We could equally well have done it the other way (provided that C is invertible) i.e.

${\displaystyle {\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}{\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}}$

Now again inverting both sides,

${\displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}^{-1}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}^{-1}{\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&0\\-C^{-1}V&I\end{bmatrix}}{\begin{bmatrix}(A-UC^{-1}V)^{-1}&0\\0&C^{-1}\end{bmatrix}}{\begin{bmatrix}I&-UC^{-1}\\0&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}(A-UC^{-1}V)^{-1}&-(A-UC^{-1}V)^{-1}UC^{-1}\\-C^{-1}V(A-UC^{-1}V)^{-1}&C^{-1}V(A-UC^{-1}V)^{-1}UC^{-1}+C^{-1}\end{bmatrix}}\qquad \mathrm {(2)} \end{aligned}}}$

Now comparing elements (1,1) of the RHS of (1) and (2) above gives the Woodbury formula

${\displaystyle \left(A-UC^{-1}V\right)^{-1}=A^{-1}+A^{-1}U(C-VA^{-1}U)^{-1}VA^{-1}.}$

src: slideplayer.com

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 + 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.

src: pbs.twimg.com

Binomial inverse theorem

The binomial inverse theorm is a more general form of the Woodbury matrix identity.

If A, U, B, V are matrices of sizes p×p, p×q, q×q, q×p, respectively, then

${\displaystyle \left(\mathbf {A} +\mathbf {UBV} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {UB} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}\mathbf {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

${\displaystyle \left(\mathbf {A} +\mathbf {UBV} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {U} \left(\mathbf {B} ^{-1}+\mathbf {VA} ^{-1}\mathbf {U} \right)^{-1}\mathbf {VA} ^{-1}.}$

This is the Woodbury matrix identity, which can also be derived using matrix blockwise inversion.

A more general formula exists when B is singular and possibly even non-square:

${\displaystyle (\mathbf {A+UBV} )^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {U} (\mathbf {I+BVA} ^{-1}\mathbf {U} )^{-1}\mathbf {BVA} ^{-1}.}$

Formulas also exist for certain cases in which A is singular.

Verification

First notice that

${\displaystyle \left(\mathbf {A} +\mathbf {UBV} \right)\mathbf {A} ^{-1}\mathbf {UB} =\mathbf {UB} +\mathbf {UBVA} ^{-1}\mathbf {UB} =\mathbf {U} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right).}$

Now multiply the matrix we wish to invert by its alleged inverse:

${\displaystyle \left(\mathbf {A} +\mathbf {UBV} \right)\left(\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {UB} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}\mathbf {BVA} ^{-1}\right)}$

${\displaystyle =\mathbf {I} _{p}+\mathbf {UBVA} ^{-1}-\mathbf {U} \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)\left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}\mathbf {BVA} ^{-1}}$

${\displaystyle =\mathbf {I} _{p}+\mathbf {UBVA} ^{-1}-\mathbf {UBVA} ^{-1}=\mathbf {I} _{p}}$

which verifies that it is the inverse.

So we get that if A^-1 and ${\displaystyle \left(\mathbf {B} +\mathbf {BVA} ^{-1}\mathbf {UB} \right)^{-1}}$ exist, then ${\displaystyle \left(\mathbf {A} +\mathbf {UBV} \right)^{-1}}$ exists and is given by the theorem above.

Special cases

First

If p = q and U = V = I_p is the identity matrix, then

${\displaystyle \left(\mathbf {A} +\mathbf {B} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\mathbf {B} \left(\mathbf {B} +\mathbf {BA} ^{-1}\mathbf {B} \right)^{-1}\mathbf {BA} ^{-1}.}$

Remembering the identity

${\displaystyle \left(\mathbf {C} \mathbf {D} \right)^{-1}=\mathbf {D} ^{-1}\mathbf {C} ^{-1},}$

we can also express the previous equation in the simpler form as

${\displaystyle \left(\mathbf {A} +\mathbf {B} \right)^{-1}=\mathbf {A} ^{-1}-\mathbf {A} ^{-1}\left(\mathbf {I} +\mathbf {B} \mathbf {A} ^{-1}\right)^{-1}\mathbf {B} \mathbf {A} ^{-1}.}$

Continuing with the merging of the terms of the far right-hand side of the above equation results in Hua's identity

${\displaystyle \left(\mathbf {A} +\mathbf {B} \right)^{-1}=\mathbf {A} ^{-1}-\left(\mathbf {A} +\mathbf {A} \mathbf {B} ^{-1}\mathbf {A} \right)^{-1}.}$

Second

If B = I_q is the identity matrix and q = 1, then U is a column vector, written u, and V is a row vector, written v^T. Then the theorem implies the Sherman-Morrison formula:

${\displaystyle \left(\mathbf {A} +\mathbf {uv} ^{\mathrm {T} }\right)^{-1}=\mathbf {A} ^{-1}-{\frac {\mathbf {A} ^{-1}\mathbf {uv} ^{\mathrm {T} }\mathbf {A} ^{-1}}{1+\mathbf {v} ^{\mathrm {T} }\mathbf {A} ^{-1}\mathbf {u} }}.}$

This is useful if one has a matrix A with a known inverse A^-1 and one needs to invert matrices of the form A+uv^T quickly for various u and v.

Third

If we set A = I_p and B = I_q, we get

${\displaystyle \left(\mathbf {I} _{p}+\mathbf {UV} \right)^{-1}=\mathbf {I} _{p}-\mathbf {U} \left(\mathbf {I} _{q}+\mathbf {VU} \right)^{-1}\mathbf {V} .}$

In particular, if q = 1, then

${\displaystyle \left(\mathbf {I} +\mathbf {uv} ^{\mathrm {T} }\right)^{-1}=\mathbf {I} -{\frac {\mathbf {uv} ^{\mathrm {T} }}{1+\mathbf {v} ^{\mathrm {T} }\mathbf {u} }},}$

which is a particular case of the Sherman-Morrison formula given above.

src: slideplayer.com

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

src: www.spiedigitallibrary.org

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 

src: slideplayer.com

External links

• Some matrix identities
• Weisstein, Eric W. "Woodbury formula". MathWorld. 

Source of the article : Wikipedia