Woodbury matrix identity

Woodbury matrix identity

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. 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.[3]

The Woodbury matrix identity is[4]

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

Contents

Derivation via blockwise elimination

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 AX + UY = I and VXC − 1Y = 0, which is equivalent to (A + UCV)X = I. Eliminating the first equation, we find that X = A − 1(IUY), which can be substituted into the second to find VA − 1(IUY) = C − 1Y. Expanding and rearranging, we have VA − 1 = (C − 1 + VA − 1U)Y, or (C − 1 + VA − 1U) − 1VA − 1 = Y. Finally, we substitute into our AX + UY = I, and we have AX + U(C − 1 + VA − 1U) − 1VA − 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.

Derivation from LDU decomposition

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 & (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{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} (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{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(C-VA^{-1}U)^{-1}VA^{-1}.

Direct proof

Just check that (A + UCV) times the RHS 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] \\
& \quad = I + UCVA^{-1} - (U+UCVA^{-1}U)(C^{-1} + VA^{-1}U)^{-1}VA^{-1} \\
& \quad = I + UCVA^{-1} - UC(C^{-1}+ VA^{-1}U)(C^{-1} + VA^{-1}U)^{-1}VA^{-1} \\
& \quad = I + UCVA^{-1} - UCVA^{-1} = I 
\end{align}

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.

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.

See also

Notes

  1. ^ Max A. Woodbury, Inverting modified matrices, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp MR38136
  2. ^ Max A. Woodbury, The Stability of Out-Input Matrices. Chicago, Ill., 1949. 5 pp. MR32564
  3. ^ Hager, William W. (1989). "Updating the inverse of a matrix". SIAM Review 31 (2): 221–239. doi:10.1137/1031049. JSTOR 2030425. MR997457. 
  4. ^ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM. p. 258. ISBN 978-0-89871-521-7. MR1927606 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Woodbury — is a common place name in the English language meaning a town in a forest. It may refer to multiple places, all in English speaking countries:*In Australia: **Woodbury, Tasmania *In England: **Woodbury, Cornwall **Woodbury, Devon **Woodbury,… …   Wikipedia

  • Woodbury — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Woodbury est un nom de toponyme commun en anglais signifiant une ville dans une forêt. Le terme peut faire référence à : En Australie : Woodbury …   Wikipédia en Français

  • Invertible matrix — In linear algebra an n by n (square) matrix A is called invertible (some authors use nonsingular or nondegenerate) if there exists an n by n matrix B such that where In denotes the n by n identity matrix and the multiplication used is ordinary… …   Wikipedia

  • 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:left(mathbf{A}+mathbf{UBV} ight)^{ 1}=mathbf{A}^{ 1}… …   Wikipedia

  • List of linear algebra topics — This is a list of linear algebra topics. See also list of matrices glossary of tensor theory. Contents 1 Linear equations 2 Matrices 3 Matrix decompositions 4 …   Wikipedia

  • Schur complement — In linear algebra and the theory of matrices,the Schur complement of a block of a matrix within alarger matrix is defined as follows.Suppose A , B , C , D are respectively p times; p , p times; q , q times; p and q times; q matrices, and D is… …   Wikipedia

  • Complément de Schur —  Ne doit pas être confondu avec la méthode du complément de Schur (en) en analyse numérique. En algèbre linéaire et plus précisément en théorie des matrices, le complément de Schur est défini comme suit. Soit …   Wikipédia en Français

  • List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… …   Wikipedia

  • Recursive least squares filter — Recursive least squares (RLS) algorithm is used in adaptive filters to find the filter coefficients that relate to recursively producing the least squares (minimum of the sum of the absolute squared) of the error signal (difference between the… …   Wikipedia

  • SMW — is an abbreviation that may stand for * Super Mario World a video game by Nintendo for the Super Nintendo Entertainment System. * SMW a non commercial Super Mario World tribute album by Xoc. * Smoky Mountain Wrestling a defunct wrestling… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”