1325 days ago Leave a comment Permalink

Invert a Matrix using the Woodbury Matrix Inverse Formula Identity

Previously I wrote about the LDU decomposition and the Schur complement. These can be further used to derive the Sherman–Morrison–Woodbury formula, otherwise known as the matrix inversion lemma, for inverting a matrix. As shown in the previous post, a UDL and LDU are two ways of factorizing a matrix:

\begin{pmatrix} V_{11} & V_{12}\\ V_{21} & V_{22}\\ \end{pmatrix}= \begin{pmatrix} 1 & V_{12}V_{22}^{-1}\\ 0 & 1\\ \end{pmatrix} \begin{pmatrix} V_{11.2} & 0 \\ 0 & V_{22} \\ \end{pmatrix} \begin{pmatrix} 1 & 0 \\ V_{22}^{-1}V_{21} & 1 \\ \end{pmatrix}

\begin{pmatrix} V_{11} & V_{12}\\ V_{21} & V_{22}\\ \end{pmatrix} = \begin{pmatrix} 1 & 0\\ V_{21}V_{11}^{-1} & 1\\ \end{pmatrix} \begin{pmatrix} V_{11} & 0 \\ 0 & V_{22.1} \\ \end{pmatrix} \begin{pmatrix} 1 & V_{11}^{-1}V_{12} \\ 0 & 1 \\ \end{pmatrix}
Now consider taking the inverse of the matrices above, yielding

\begin{pmatrix} V_{11} & V_{12}\\ V_{21} & V_{22}\\ \end{pmatrix}^{-1}= \begin{pmatrix} 1 & 0 \\ -V_{22}^{-1}V_{21} & 1 \\ \end{pmatrix} \begin{pmatrix} V_{11.2}^{-1} & 0 \\ 0 & V_{22}^{-1} \\ \end{pmatrix} \begin{pmatrix} 1 & -V_{12}V_{22}^{-1}\\ 0 & 1\\ \end{pmatrix}

\begin{pmatrix} V_{11} & V_{12}\\ V_{21} & V_{22}\\ \end{pmatrix}^{-1} = \begin{pmatrix} 1 & -V_{11}^{-1}V_{12} \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} V_{11}^{-1} & 0 \\ 0 & V_{22.1}^{-1} \\ \end{pmatrix} \begin{pmatrix} 1 & 0\\ -V_{21}V_{11}^{-1} & 1\\ \end{pmatrix}
Multiplying the matrices on the RHS yields
\begin{pmatrix} V_{11} & V_{12}\\ V_{21} & V_{22}\\ \end{pmatrix}^{-1} = \begin{pmatrix} V_{11.2}^{-1} & -V_{11.2}^{-1}V_{12}V_{22}^{-1}\\ -V_{22}^{-1}V_{21}V_{11.2}^{-1} & V_{22}^{-1}+V_{22}^{-1}V_{21}V_{11.2}^{-1}V_{12}V_{22}^{-1} \end{pmatrix}

\begin{pmatrix} V_{11} & V_{12}\\ V_{21} & V_{22}\\ \end{pmatrix}^{-1} =\begin{pmatrix} V_{11}^{-1}+V_{11}^{-1}V_{12}V_{22.1}^{-1}V_{21}V_{11}^{-1} & -V_{11}^{-1}V_{12}V_{22.1}^{-1}\\ -V_{22.1}^{-1}V_{21}V_{11}^{-1} & V_{22.1}^{-1} \end{pmatrix}
These two results can be used to form neat expressions for the inverse of a partitioned block matrix. It follows that
\begin{pmatrix} V_{11.2}^{-1} & -V_{11.2}^{-1}V_{12}V_{22}^{-1}\\ -V_{22}^{-1}V_{21}V_{11.2}^{-1} & V_{22}^{-1}+V_{22}^{-1}V_{21}V_{11.2}^{-1}V_{12}V_{22}^{-1} \end{pmatrix}= \begin{pmatrix} V_{11}^{-1}+V_{11}^{-1}V_{12}V_{22.1}^{-1}V_{21}V_{11}^{-1} & -V_{11}^{-1}V_{12}V_{22.1}^{-1}\\ -V_{22.1}^{-1}V_{21}V_{11}^{-1} & V_{22.1}^{-1} \end{pmatrix}
The equality holds for each block or element, so two expressions can be found for the Woodbury matrix inverse formula, namely:
V_{11.2}^{-1}=V_{11}^{-1}+V_{11}^{-1}V_{12}V_{22.1}^{-1}V_{21}V_{11}^{-1}
and
V_{22.1}^{-1}=V_{22}^{-1}+V_{22}^{-1}V_{21}V_{11.2}^{-1}V_{12}V_{22}^{-1}
where the dot notation corresponds to the Schur complement i.e.
V_{11.2}=V_{11}-V_{12}V_{22}^{-1}V_{21}\\ V_{22.1}=V_{22}-V_{21}V_{11}^{-1}V_{12}\\
An application of the Woodbury matrix inverse can be found in deriving conditional distributions for multivariate normals.