7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Matrix inversion Lemma rule which are given in RLS equations(in most books eg Adaptive Filter Theory,Advance Digital Signal Processing and Noise reduction) are some what different from the standard rule given below. en.wikipedia.org/wiki/Woodbury_matrix_identity I am not able to relate them.Can you please help me what assumptions are being taken. $\endgroup$
    – Abhi
    Oct 28, 2016 at 1:37
  • $\begingroup$ Please update your question with a) the MIL given for RLS equations vs the Woodbury derivation that you cannot reconcile it with. I'll reopen once I can read everything on this page. Also, the actual question may be off-topic for SE.SP... if so, I'll migrate it to somewhere better. $\endgroup$
    – Peter K.
    Oct 28, 2016 at 11:56
  • $\begingroup$ Are you after the derivation of the Sequential Least Squares using the Matrix Inversion Lemma or are you after a proof for MIL? $\endgroup$
    – Royi
    Jun 26, 2019 at 9:24

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ While you've proved that it is true, the OP asked for the derivation. How would you derive it if you didn't already know the answer? $\endgroup$
    – David
    Dec 1, 2021 at 20:26
  • 1
    $\begingroup$ @David, This is a valid derivation. Many times derivations in Math starts with: "Assume we're right and let's go backward". $\endgroup$
    – Royi
    Dec 1, 2021 at 20:58
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.