Woodbury matrix identity

From Free net encyclopedia

In mathematics (specifically linear algebra), the Woodbury matrix identity 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.

Explicitly, the Woodbury matrix identity is

<math> \left(A+UCV \right)^{-1} = A^{-1} - A^{-1}U \left(C^{-1}+VA^{-1}U \right)^{-1} VA^{-1}, </math>

where A, U, C and V all denote matrices of the correct size. Specifically, A is n-by-n, U is n-by-k, C is k-by-k and V is k-by-n.

In the special case where C is the 1-by-1 unit matrix, reduces to the Sherman-Morrison formula.

1 Applications
2 See also
3 References
4 External links

[edit]

Applications

This identity is useful in certain numerical computations where A⁻¹ has already been computed and it is desired to compute (A + UCV)⁻¹. With the inverse of A available, it is only necessary to find the inverse of C⁻¹+VA⁻¹U 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.

This is applied, e.g., in the Kalman filter and other least-squares estimation 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.

[edit]