Recursive least squares filter

Recursive least squares (RLS) is an adaptive filter algorithm that recursively finds the coefficients that minimize a weighted linear least squares cost function relating to the input signals. This approach is in contrast to other algorithms such as the least mean squares (LMS) that aim to reduce the mean square error. In the derivation of the RLS, the input signals are considered deterministic, while for the LMS and similar algorithms they are considered stochastic. Compared to most of its competitors, the RLS exhibits extremely fast convergence. However, this benefit comes at the cost of high computational complexity.

RLS was discovered by Gauss but lay unused or ignored until 1950 when Plackett rediscovered the original work of Gauss from 1821. In general, the RLS can be used to solve any problem that can be solved by adaptive filters. For example, suppose that a signal ${\displaystyle d(n)}$ is transmitted over an echoey, noisy channel that causes it to be received as

where ${\displaystyle v(n)}$ represents additive noise. The intent of the RLS filter is to recover the desired signal ${\displaystyle d(n)}$ by use of a ${\displaystyle p+1}$-tap FIR filter, ${\displaystyle \mathbf {w} }$:

where ${\displaystyle \mathbf {x} _{n}=[x(n)\quad x(n-1)\quad \ldots \quad x(n-p)]^{T}}$ is the column vector containing the ${\displaystyle p+1}$ most recent samples of ${\displaystyle x(n)}$. The estimate of the recovered desired signal is

The goal is to estimate the parameters of the filter ${\displaystyle \mathbf {w} }$, and at each time ${\displaystyle n}$ we refer to the current estimate as ${\displaystyle \mathbf {w} _{n}}$ and the adapted least-squares estimate by ${\displaystyle \mathbf {w} _{n+1}}$. ${\displaystyle \mathbf {w} _{n}}$ is also a column vector, as shown below, and the transpose, ${\displaystyle \mathbf {w} _{n}^{\mathit {T}}}$, is a row vector. The matrix product ${\displaystyle \mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}}$ (which is the dot product of ${\displaystyle \mathbf {w} _{n}}$ and ${\displaystyle \mathbf {x} _{n}}$) is ${\displaystyle {\hat {d}}(n)}$, a scalar. The estimate is "good" if ${\displaystyle {\hat {d}}(n)-d(n)}$ is small in magnitude in some least squares sense.

As time evolves, it is desired to avoid completely redoing the least squares algorithm to find the new estimate for ${\displaystyle \mathbf {w} _{n+1}}$, in terms of ${\displaystyle \mathbf {w} _{n}}$.

The benefit of the RLS algorithm is that there is no need to invert matrices, thereby saving computational cost. Another advantage is that it provides intuition behind such results as the Kalman filter.

The idea behind RLS filters is to minimize a cost function ${\displaystyle C}$ by appropriately selecting the filter coefficients ${\displaystyle \mathbf {w} _{n}}$, updating the filter as new data arrives. The error signal ${\displaystyle e(n)}$ and desired signal ${\displaystyle d(n)}$ are defined in the negative feedback diagram below: