Woodbury matrix identity

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: \left(I + UV \right)^{-1} = I - U \left(I + VU \right)^{-1} V. To recover the original equation from this reduced identity, replace U by A^{-1}U and V by 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, thus, (I + P)^{-1} = I-(I + P)^{-1}P, and similarly (I + P)^{-1} = I - P (I + P)^{-1}. The second identity is the so-called push-through identity Since B is invertible, the two B terms flanking the parenthetical quantity inverse in the right-hand side can be replaced with which results in the original Woodbury identity. A variation for when B is singular and possibly even non-square: 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 and C are positive semidefinite, and V = U^\mathrm H (implying that A + UCV is itself positive semidefinite), then the following formula provides a generalization: \begin{align} \left(XX^\mathrm H + YY^\mathrm H\right)^+ &= \left(ZZ^\mathrm H\right)^+ + \left(I - YZ^+\right)^\mathrm H X^{+\mathrm H} E X^+ \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{align} where A + UCU^\mathrm H can be written as XX^\mathrm H + YY^\mathrm H because any positive semidefinite matrix is equal to MM^\mathrm H for some M. == Derivations ==

Direct proof The formula can be proven by checking that (A + UCV) times its alleged inverse on the right side of the Woodbury identity gives the identity matrix: \begin{align} & \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{align} Alternative proofs First consider these useful identities, \begin{align} U + UCV A^{-1} U &= UC \left(C^{-1} + V A^{-1} U\right) = \left(A + UCV\right) A^{-1} U \\ \left(A + UCV\right)^{-1} U C &= A^{-1}U \left(C^{-1} + VA^{-1} U\right) ^{-1} \end{align} Now, \begin{align} 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{align} Deriving the Woodbury matrix identity is easily done by solving the following block matrix inversion problem \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 \begin{cases} AX + UY = I \\ VX - C^{-1}Y = 0\end{cases} which is equivalent to (A + UCV)X = I. Eliminating the first equation, we find that X = A^{-1}(I - UY), which can be substituted into the second to find VA^{-1}(I - UY) = C^{-1}Y. Expanding and rearranging, we have VA^{-1} = \left(C^{-1} + VA^{-1}U\right)Y, or \left(C^{-1} + VA^{-1}U\right)^{-1}VA^{-1} = Y. Finally, we substitute into our AX + UY = I, and we have AX + U\left(C^{-1} + VA^{-1}U\right)^{-1}VA^{-1} = I. Thus, :(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. We start by the matrix \begin{bmatrix} A & U \\ V & C \end{bmatrix} By eliminating the entry under the A (given that A is invertible) we get \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 \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 \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 \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 \begin{align} \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 & \left(C - VA^{-1}U\right)^{-1} \end{bmatrix} \begin{bmatrix} I & 0 \\ -VA^{-1} & I \end{bmatrix} \\[8pt] &= \begin{bmatrix} A^{-1} + A^{-1}U\left(C - VA^{-1}U\right)^{-1}VA^{-1} & -A^{-1}U\left(C - VA^{-1}U\right)^{-1} \\ -\left(C - VA^{-1}U\right)^{-1}VA^{-1} & \left(C - VA^{-1}U\right)^{-1} \end{bmatrix} \qquad\mathrm{(1)} \end{align} We could equally well have done it the other way (provided that C is invertible) i.e. \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, \begin{align} \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} \left(A - UC^{-1}V\right)^{-1} & 0 \\ 0 & C^{-1} \end{bmatrix} \begin{bmatrix} I & -UC^{-1} \\ 0 & I \end{bmatrix} \\[8pt] &= \begin{bmatrix} \left(A - UC^{-1}V\right)^{-1} & -\left(A - UC^{-1}V\right)^{-1}UC^{-1} \\ -C^{-1}V\left(A - UC^{-1}V\right)^{-1} & C^{-1} + C^{-1}V\left(A - UC^{-1}V\right)^{-1}UC^{-1} \end{bmatrix} \qquad\mathrm{(2)} \end{align} Now comparing elements (1, 1) of the RHS of (1) and (2) above gives the Woodbury formula \left(A - UC^{-1}V\right)^{-1} = A^{-1} + A^{-1}U\left(C - VA^{-1}U\right)^{-1}VA^{-1}. == 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+VA^{-1}U is known in numerical linear algebra and numerical partial differential equations as the capacitance matrix. ==See also==