In mathematics, specifically linear algebra, the Woodbury matrix identity – named after Max A. Woodbury[1][2] – 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.
However, the identity appeared in several papers before the Woodbury report.
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.
There are no published results concerning its error bounds.
Anecdotal evidence[6] suggests that it may diverge even for seemingly benign examples (when both the original and modified matrices are well-conditioned).
To recover the original equation from this reduced identity, replace
are vectors, the identity reduces to the Sherman–Morrison formula.
In the scalar case, the reduced version is simply
Continuing with the merging of the terms of the far right-hand side of the above equation results in Hua's identity
is singular, and has a recursive structure that yields
[7] 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:[7]
Formulas also exist for certain cases in which A is singular.
[8] In general Woodbury's identity is not valid if one or more inverses are replaced by (Moore–Penrose) pseudoinverses.
is itself positive semidefinite), then the following formula provides a generalization:[9][10]
because any positive semidefinite matrix is equal to
times its alleged inverse on the right side of the Woodbury identity gives the identity matrix:
Deriving the Woodbury matrix identity is easily done by solving the following block matrix inversion problem
Thus, We have derived the Woodbury matrix identity.
which is the LDU decomposition of the block matrix into an upper triangular, diagonal, and lower triangular matrices.
Now comparing elements (1, 1) of the RHS of (1) and (2) above gives the Woodbury formula
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.
is known in numerical linear algebra and numerical partial differential equations as the capacitance matrix.