3
$\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$

1 Answer 1

7
$\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$
9
  • $\begingroup$ Wow! To much! I accept this answer because you have right, but still...I don't understand the answer. $\endgroup$
    – euraad
    Jul 1, 2018 at 11:04
  • $\begingroup$ @DanielMårtensson What do you not understand? You are familiar with the normal least squares solution? $\endgroup$ Jul 1, 2018 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$
    – euraad
    Jul 1, 2018 at 20:06
  • $\begingroup$ @DanielMårtensson That is basically the matrix inside the inverse of equation $(4)$. $\endgroup$ Jul 1, 2018 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$ Jul 1, 2018 at 20:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .