# What's the idea behind recursive least squares (RLS)?

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?

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}

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