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.
$\begingroup$
$\endgroup$
-
3$\begingroup$ Because, as you know, customarily its the result what you need in RLS (or any other engineering application of it) and not the derivation of matrix inversion Lemma. (You can of course check its validity by comparing its output to a usual matrix inversion). So then what's your purpose in deriving that? May be math.se is a more proper place for purely mathematical concerns, at least for the inversion lemma. Of course its derivation is given in some papers, but just for those who are curious about it :) $\endgroup$ – Fat32 Oct 28 '16 at 0:02
-
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 '16 at 1:37
-
$\begingroup$ I suggest that you follow your book. The more general mathematical treatment shall not concern you from the applications point of view. There's no mystery about the proof. What is interesting is that historically this lemma was originally related to another lost, forgotton theorem, which the theorem is forgetten but its lemma stays useful. That's why people call it a funny thing :) nothing special but quite useful. $\endgroup$ – Fat32 Oct 28 '16 at 2:25
-
$\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 '16 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 '19 at 9:24
$\begingroup$
$\endgroup$
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.
