In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 (specifically linear algebra

Linear algebra

Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...

), the Woodbury matrix identity, named after Max A. Woodbury says that the inverse of a rank-k correction of some matrix

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 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
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. This can be derived using blockwise matrix inversion.

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

Sherman–Morrison formula

In mathematics, in particular linear algebra, the Sherman–Morrison formula, named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an invertiblematrix Aand the dyadic product, u v^T,of a column vector u and a row vector v^T...

.

Derivation via blockwise elimination

Deriving the Woodbury matrix identity is easily done by solving the following block matrix inversion problem
Expanding, we can see that the above reduces to and , which is equivalent to . Eliminating the first equation, we find that , which can be substituted into the second to find . Expanding and rearranging, we have , or . Finally, we substitute into our , and we have . Thus,
We have derived the Woodbury matrix identity.

Derivation from LDU decomposition

We start by the matrix
By eliminating the entry under the A (given that A is invertible) we get


Likewise, eliminating the entry above C gives


Now combining the above two, we get


Moving to the right side gives

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

Now inverting both sides gives

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

Now again inverting both sides,

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

Direct proof

Just check that times the RHS of the Woodbury identity gives the identity matrix:

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

Kalman filter

In statistics, the Kalman filter is a mathematical method named after Rudolf E. Kálmán. Its purpose is to use measurements observed over time, containing noise and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated...

 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.

See also

• Invertible matrix
• Schur complement
  Schur complement
  In linear algebra and the theory of matrices,the Schur complement of a matrix block is defined as follows.Suppose A, B, C, D are respectivelyp×p, p×q, q×p...
  
  
• Matrix determinant lemma
  Matrix determinant lemma
  In mathematics, in particular linear algebra, the matrix determinant lemma computes the determinant of the sum of an invertiblematrix Aand the dyadic product, u vT,of a column vector u and a row vector vT.- Statement :...
  
  , formula for a rank-k update to a determinant
  Determinant
  In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...
  
  
• Binomial inverse theorem
  Binomial inverse theorem
  In mathematics, the Binomial Inverse Theorem is useful for expressing matrix inverses in different ways.If A, U, B, V are matrices of sizes p×p, p×q, q×q, q×p, respectively, then...
  
  ; slightly more general identity.

External links

• Some matrix identities

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.