2
$\begingroup$

The simply explanation of recursive Least squares (RLS) is:

$$\theta(t) = \theta(t-1) -P(t)\phi(t)[y(t) - \theta ^T(t)\theta(t-1)]$$ $$P^{-1}(t) = P^{-1} + \phi(t) \phi^T(t)$$

Where $\phi$ is the regression vector. I understand that this is the error of measurement:

$$y(t) - \theta ^T(t)\theta(t-1)$$

And this is the error of parameter $\theta$

$$P(t)\phi(t)[y(t) - \theta ^T(t)\theta(t-1)]$$

But my question is. Why are $P$ as this:

$$P^{-1}(t) = P^{-1} + \phi(t) \phi^T(t)$$

??

$P(t)$ will be a matrix, but why a matrix? Why not a scalar? What's the idea behind this formula ?

$$P^{-1}(t) = P^{-1}(t-1) + \phi(t) \phi^T(t)$$

Why inverse?

$\endgroup$
4
$\begingroup$

Recursive least squares tries to identify the parameter $\theta$ which satisfies the following relation

$$ z = \phi^\top\,\theta, \tag{1} $$

where $z$ and $\phi$ are known. When assuming that $n$ data points are known then equation $(1)$ can be extended to the following equation

$$ \underbrace{ \begin{bmatrix} z_1 \\ z_2 \\ \vdots \\ z_n \end{bmatrix} }_{Z_n} = \underbrace{ \begin{bmatrix} \phi^\top_1 \\ \phi^\top_2 \\ \vdots \\ \phi^\top_n \end{bmatrix} }_{\Phi_n} \theta. \tag{2} $$

The normal least squares solution for $\theta$ would then be

$$ \hat{\theta}_n = \left(\Phi_n^\top\,\Phi_n\right)^{-1}\,\Phi_n^\top\,Z_n \tag{3} $$

Using the definition of $Z_n$ and $\Phi_n$ in equation $(2)$ then $Z_{n+1}$ and $\Phi_{n+1}$ can be written as

$$ Z_{n+1} = \begin{bmatrix} Z_n \\ z_{n+1} \end{bmatrix}, \quad \Phi_{n+1} = \begin{bmatrix} \Phi_n \\ \phi_{n+1}^\top \end{bmatrix}, $$

so the least squares solution using $n+1$ points can also be written as

$$ \begin{align} \hat{\theta}_{n+1} &= \left(\Phi_{n+1}^\top\,\Phi_{n+1}\right)^{-1}\,\Phi_{n+1}^\top\,Z_{n+1}, \\ &= \left(\Phi_n^\top\,\Phi_n + \phi_{n+1}\,\phi_{n+1}^\top\right)^{-1}\,\left(\Phi_n^\top\,Z_n + \phi_{n+1}\,z_{n+1}\right). \end{align} \tag{4} $$

By defining $P_n = \left(\Phi_n^\top\,\Phi_n\right)^{-1}$ then, using the Woodbury matrix identity, $P_{n+1}$ can be written as

$$ \begin{align} P_{n+1} &= \left(\Phi_n^\top\,\Phi_n + \phi_{n+1}\,\phi_{n+1}^\top\right)^{-1}, \\ &= P_n - P_n\,\phi_{n+1}\,\left(1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}\right)^{-1}\,\phi_{n+1}^\top\,P_n, \end{align} $$

since $1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}$ is scalar it can also be written as

$$ P_{n+1} = P_n - \frac{P_n\,\phi_{n+1}\,\phi_{n+1}^\top\,P_n}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}} = \left(I - \frac{P_n\,\phi_{n+1}\,\phi_{n+1}^\top}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\right) P_n. \tag{5} $$

Substituting equation $(5)$ into equation $(4)$ gives

$$ \hat{\theta}_{n+1} = \left(I - \frac{P_n\,\phi_{n+1}\,\phi_{n+1}^\top}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\right) P_n\,\left(\Phi_n^\top\,Z_n + \phi_{n+1}\,z_{n+1}\right). $$

By substituting $P_n$ into equation $(3)$ then it can be shown that $\hat{\theta}_n = P_n\,\Phi^\top_n\,Z_n$, so the above equation can also be written as

$$ \hat{\theta}_{n+1} = \left(I - \frac{P_n\,\phi_{n+1}\,\phi_{n+1}^\top}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\right) \left(\hat{\theta}_n + P_n\,\phi_{n+1}\,z_{n+1}\right), $$

which does no longer contain $Z_n$ or $\Phi_n$, which makes it recursive. Expanding the brackets of the above equation and simplifying the resulting equation gives

$$ \begin{align} \hat{\theta}_{n+1} &= \hat{\theta}_n + P_n\,\phi_{n+1}\,z_{n+1} - \frac{P_n\,\phi_{n+1}\,\phi_{n+1}^\top \left(\hat{\theta}_n + P_n\,\phi_{n+1}\,z_{n+1}\right)}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}, \\ &= \hat{\theta}_n + P_n\,\phi_{n+1}\left(z_{n+1} - \frac{\phi_{n+1}^\top \hat{\theta}_n}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}} - \frac{\phi_{n+1}^\top\,P_n\,\phi_{n+1}}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\,z_{n+1}\right), \\ &= \hat{\theta}_n + P_n\,\phi_{n+1}\left(\frac{z_{n+1}}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}} - \frac{\phi_{n+1}^\top \hat{\theta}_n}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\right), \\ &= \hat{\theta}_n + \frac{P_n\,\phi_{n+1}}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}} \left(z_{n+1} - \phi_{n+1}^\top\,\hat{\theta}_n\right). \\ \end{align} $$

There are common terms in both $P_{n+1}$ and $\hat{\theta}_{n+1}$, so in order to avoid calculating the same thing twice one often defines the update law as

$$ \left\{ \begin{align} K_n &= \frac{P_n\,\phi_{n+1}}{1 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}} \\ P_{n+1} &= P_n - K_n\,\phi_{n+1}^\top\,P_n \\ \hat{\theta}_{n+1} &= \hat{\theta}_n + K_n \left(z_{n+1} - \phi_{n+1}^\top\,\hat{\theta}_n\right) \end{align} \right. \tag{6} $$


Often however a forgetting factor is used as well, which weighs "old data" less and less the "older" it gets. Basically the solution to the least squares in equation $(3)$ is turned into a weighted least squares with exponentially decaying weights. One way of writing this is by changing equation $(2)$ into

$$ \underbrace{ \begin{bmatrix} \alpha^{n-1}\,z_1 \\ \alpha^{n-2}\,z_2 \\ \vdots \\ z_n \end{bmatrix} }_{Z_n} = \underbrace{ \begin{bmatrix} \alpha^{n-1}\,\phi^\top_1 \\ \alpha^{n-2}\,\phi^\top_2 \\ \vdots \\ \phi^\top_n \end{bmatrix} }_{\Phi_n} \theta, \tag{7} $$

where it can be noted that $0<\alpha\leq1$. An equivalent solution would be to use a diagonal weighting matrix with $\begin{bmatrix}\alpha^{n-1} & \alpha^{n-2} & \cdots & 1\end{bmatrix}$ on its diagonal. By now using the definition of $Z_n$ and $\Phi_n$ in equation $(7)$ then $Z_{n+1}$ and $\Phi_{n+1}$ can be written as

$$ Z_{n+1} = \begin{bmatrix} \alpha\,Z_n \\ z_{n+1} \end{bmatrix}, \quad \Phi_{n+1} = \begin{bmatrix} \alpha\,\Phi_n \\ \phi_{n+1}^\top \end{bmatrix}. $$

The end result of equation $(4)$ now becomes

$$ \hat{\theta}_{n+1} = \left(\alpha^2\,\Phi_n^\top\,\Phi_n + \phi_{n+1}\,\phi_{n+1}^\top\right)^{-1}\,\left(\alpha^2\,\Phi_n^\top\,Z_n + \phi_{n+1}\,z_{n+1}\right). \tag{8} $$

Similarly equation $(5)$ becomes

$$ P_{n+1} = \alpha^{-2}\,\left(P_n - \frac{P_n\,\phi_{n+1}\,\phi_{n+1}^\top\,P_n}{\alpha^2 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\right) = \alpha^{-2}\,\left(I - \frac{P_n\,\phi_{n+1}\,\phi_{n+1}^\top}{\alpha^2 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\right)\,P_n. \tag{9} $$

By substituting equation $(9)$ into equation $(8)$ and expanding and simplifying it yields

$$ \hat{\theta}_{n+1} = \hat{\theta}_n + \frac{P_n\,\phi_{n+1}}{\alpha^2 + \phi_{n+1}^\top\,P_n\,\phi_{n+1}}\,\left(z_{n+1} - \phi_{n+1}^\top\,\hat{\theta}_n\right). \tag{10} $$

Since the weight factor $\alpha$ only appears squared one often defines the forgetting factor parameter as $\lambda = \alpha^2$. By again factoring out the common term then the following update law can be obtained

$$ \left\{ \begin{align} K_n &= \frac{P_n\,\phi_{n+1}}{\lambda + \phi_{n+1}^\top\,P_n\,\phi_{n+1}} \\ P_{n+1} &= \lambda^{-1} \left(P_n - K_n\,\phi_{n+1}^\top\,P_n\right) \\ \hat{\theta}_{n+1} &= \hat{\theta}_n + K_n \left(z_{n+1} - \phi_{n+1}^\top\,\hat{\theta}_n\right) \end{align} \right. \tag{11} $$

$\endgroup$
  • $\begingroup$ Wow! To much! I accept this answer because you have right, but still...I don't understand the answer. $\endgroup$ – Daniel Mårtensson Jul 1 '18 at 11:04
  • $\begingroup$ @DanielMårtensson What do you not understand? You are familiar with the normal least squares solution? $\endgroup$ – Kwin van der Veen Jul 1 '18 at 11:50
  • $\begingroup$ No, I just asking why does $P$ will be described as: $$P^{-1}(t) = P^{-1}(t-1) + \phi(t) \phi^T(t)$$ What's the idea behind to create a matrix of the the regresson vector $\phi(t) \phi^T(t)$ ? Why inverse? $\endgroup$ – Daniel Mårtensson Jul 1 '18 at 20:06
  • $\begingroup$ @DanielMårtensson That is basically the matrix inside the inverse of equation $(4)$. $\endgroup$ – Kwin van der Veen Jul 1 '18 at 20:14
  • $\begingroup$ @DanielMårtensson Namely: $$ \Phi_{n+1}^\top\,\Phi_{n+1} = \begin{bmatrix} \Phi_n^\top & \phi_{n+1} \end{bmatrix} \begin{bmatrix} \Phi_n \\ \phi_{n+1}^\top \end{bmatrix} = \Phi_n^\top\,\Phi_n + \phi_{n+1}\,\phi_{n+1}^\top $$ $\endgroup$ – Kwin van der Veen Jul 1 '18 at 20:18

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.