Deriving the Matrix Inversion Lemma for RLS Equations vs the Woodbury Derivation

Question

Can any one help me in deriving the matrix inversion lemma rule for RLS algorithm?

I don't know how to start with. Many books have just stated but they haven't derived it.

Answer 1

It is not clear what are you asking but I will try answer both things.

Deriving the Matrix Inversion Lemma

The Matrix Inversion Lemma goes as:

$$ {\left( A + U C V \right)}^{-1} = {A}^{-1} - {A}^{-1} U {\left( {C}^{-1} + V {A}^{-1} U \right)}^{-1} V {A}^{-1} $$

Deriving it is by utilizing these useful identities: $$\begin{align} U + U C V {A}^{-1} U & = U C \left( {C}^{-1} + V {A}^{-1} U \right) = \left(A + U C V \right) A^{-1} U \label{auxEqn001}\tag{1} \\ {\left( A + U C V \right)}^{-1} U C & = {A}^{-1} U {\left( {C}^{-1} + V {A}^{-1} U \right)} ^{-1} \label{auxEqn002}\tag{2} \end{align}$$

Where $ \ref{auxEqn002} $ comes from $ \ref{auxEqn001} $ by multiplying the 2 last terms by $ {\left(A + U C V \right)}^{-1} $ on the left and $ {\left( {C}^{-1} + V {A}^{-1} U \right)}^{-1} $ on the right.

Then it is straight forward: $$\begin{align} {A}^{-1} &= {\left( A + U C V \right)}^{-1} \left( A + U C V \right) {A}^{-1} && \text{As $ {\left( A + U C V \right)}^{-1} \left( A + UCV \right) = I $} \\ & = \left( A + U C V \right)^{-1} \left( I + UCVA^{-1} \right) \\ & = \left( A + U C V \right)^{-1} + \left( A + U C V \right)^{-1} U C V {A}^{-1} && \text{Multiplying the terms} \\ & = \left( A + U C V \right)^{-1} + {A}^{-1} U {\left( {C}^{-1} + V {A}^{-1} U \right)}^{-1} V {A}^{-1} && \text{Utilizing \ref{auxEqn002}} \\ & \Rightarrow {\left( A + U C V \right)}^{-1} = {A}^{-1} - {A}^{-1} U {\left( {C}^{-1} + V {A}^{-1} U \right)}^{-1} VA^{-1} \end{align}$$

The nice thing is we don't need the Matrix Inversion Lemma (Woodbury Matrix Identity) for the Sequential Form of the Linear Least Squares but we can do with a special case of it called Sherman Morrison Formula:

$$ {\left( A + u {v}^{T} \right)}^{-1} = {A}^{-1} - \frac{ {A}^{-1} u {v}^{T} {A}^{-1} }{ 1 + {v}^{T} {A}^{-1} u } $$

The Sherman Morrison Formula is the MIL where $ C = I $, $ U = u $ and $ V = {v}^{T} $.

Deriving the Sequential form of the Linear Least Squares Estimator

In Sequential Form of the Least Squares Estimator for Linear Least Squares Model I derived the sequential form. To add something new I will extend the derivation to the Weighted Linear Least Squares Estimator.

Answer 2

I'm not sure if the OP was looking for a proof or derivation. In my mind a derivation is bit different than what Royi provided. I have looked for but never seen a derivation of the various versions of the Matrix Inversion lemma. Usually, the proof is left as an exercise for the reader.

So I offer the following derivation based on partitioned matrices. The only assumption is that the matrices $A$ and $D$ have defined inverses. $$ \left[\begin{array}{cc} A & B\\ C & D \end{array}\right]\left[\begin{array}{cc} U & V\\ W & X \end{array}\right]=\left[\begin{array}{cc} I & 0\\ 0 & I \end{array}\right] $$ We wish to find the matrices $U,V,W,X$ such that they provide an inverse to the block matrix defined by $A,B,C,D$.

The above equation can be expanded into the following set of equations: \begin{equation} AU+BW=I \end{equation} \begin{equation} AV+BX=0 \end{equation} \begin{equation} CU+DW=0 \end{equation} \begin{equation} CV+DX=I \end{equation}

First we solve for $W$ \begin{equation} \begin{split}DW & =-CU\\ W & =-D^{-1}CU \end{split} \end{equation} Solving for $U$ leads to \begin{equation} \begin{split}U & =A^{-1}-A^{-1}BW\\ U & =A^{-1}+A^{-1}BD^{-1}CU\\ (I-A^{-1}BD^{-1}C)U & =A^{-1}\\ U & =(I-A^{-1}BD^{-1}C)^{-1}A^{-1}\\ U & =(A-BD^{-1}C)^{-1} \end{split} \end{equation}

Now we can use the other two equations to solve to $V$ and $X$. Solving for $V$ gives \begin{equation} \begin{split}AV & =-BX\\ V & =-A^{-1}BX \end{split} \end{equation} Solving for $X$ gives \begin{equation} \begin{split}X & =D^{-1}-D^{-1}CV\\ X & =D^{-1}+D^{-1}CA^{-1}BX\\ (I-D^{-1}CA^{-1}B)X & =D^{-1}\\ X & =(I-D^{-1}CA^{-1}B)D^{-1}\\ & =(D-CA^{-1}B)^{-1} \end{split} \end{equation}

Now we can also solve \begin{equation} \left[\begin{array}{cc} U & V\\ W & X \end{array}\right]\left[\begin{array}{cc} A & B\\ C & D \end{array}\right]=\left[\begin{array}{cc} I & 0\\ 0 & I \end{array}\right] \end{equation} but we only need one equation from this - we need an alternative expression for $W$. Therefore \begin{equation} WA+XC=0 \end{equation} Solving $W$ gives \begin{equation} \begin{split}W & =-XCA^{-1}\\ & =-(D-CA^{-1}B)^{-1}CA^{-1} \end{split} \end{equation} where we have used the previous expression for $X$. Substituting this back into the expression for $U$ gives \begin{equation} \begin{split}U & =A^{-1}-A^{-1}BW\\ & =A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} \end{split} \end{equation} Using the previous solution for $U$ gives \begin{equation} (A-BD^{-1}C)^{-1}=A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} \end{equation} The more conventional form is arrived at by letting $B=-B$ to give \begin{equation} (A+BD^{-1}C)^{-1}=A^{-1}-A^{-1}B(D+CA^{-1}B)^{-1}CA^{-1} \end{equation}

The other versions of the Matrix Inversion lemma can be found by either manipulating these equations or by letting $B$, $C$, $D$ have the appropriate dimensions.