- Recursive least squares filter
Recursive least squares (RLS)
algorithm is used inadaptive filter s to find the filter coefficients that relate to recursively producing the least squares (minimum of the sum of the absolute squared) of the error signal (difference between the desired and the actual signal). This is contrast to other algorithms that aim to reduce themean square error . The difference is that RLS filters are dependent on the signals themselves, whereas MSE filters are dependent on their statistics (specifically, the autocorrelation of the input and the cross-correlation of the input and desired signals). If these statistics are known, an MSE filter with fixed co-efficients (i.e., independent of the incoming data) can be built.Motivation
Suppose that a signal mathbf{d} is transmitted over an echoey,
noisy channel that causes it to be received as:x(n)=sum_{k=0}^q b_n(k) d(n-k)+v(n)
where v(n) represents
white noise . We will attempt to recover the desired signal mathbf{d} by use of anFIR filter, mathbf{w}::hat{d}(n) = y(n) = mathbf{w}_n^mathit{T} mathbf{x}(n)
Our goal is to estimate the parameters of the filter mathbf{w}, and at each time "n" we refer to the new least squares estimate by mathbf{w_n}. As time evolves, we would like to avoid completely redoing the least squares algorithm to find the new estimate for mathbf{w}_{n+1}, in terms of mathbf{w}_n.
The benefit of the RLS algorithm is that there is no need to invert matrices, thereby saving computational power. Another advantage is that it provides intuition behind such results as the
Kalman filter .Discussion
The idea behind RLS filters is to minimize a
cost function C by appropriately selecting the filter coefficients mathbf{w}_n, updating the filter as new data arrives. The error signal e(n) and desired signal d(n) are defined in thenegative feedback diagram below:The error implicitly depends on the filter coefficients through the estimate hat{d}(n):
:e(n)=d(n)-hat{d}(n)
The weighted least squares error function C—the cost function we desire to minimize—being a function of e(n) is therefore also dependent on the filter coefficients::C(mathbf{mathbf{w}_n})=sum_{i=0}^{n}lambda^{n-i}|e(i)|^{2}=sum_{i=0}^{n}lambda^{n-i}e(i),e^{*}(i)where 0
is an exponential weighting factor which effectively limits the number of input samples based on which the cost function is minimized. The cost function is minimized by taking the partial derivatives for all entries k of the coefficient vector mathbf{w}_{n} and setting the results to zero:frac{partial C(mathbf{w}_{n})}{partial w^{*}_{n}(k)}=sum_{i=0}^{n}lambda^{n-i}e(i),frac{partial e^{*}(i)}{partial w^{*}_{n}(k)}=sum_{i=0}^{n}lambda^{n-i}e(i),x^{*}(i-k)=0 Next, replace e(n) with the definition of the error signal:sum_{i=0}^{n}lambda^{n-i}left [d(i)-sum_{l=0}^{p}w_{n}(l)x(i-l) ight] x^{*}(i-k)= 0 Rearranging the equation yields:sum_{l=0}^{p}w_{n}(l)left [sum_{i=0}^{n}lambda^{n-i},x(i-l)x^{*}(i-k) ight] = sum_{i=0}^{n}lambda^{n-i}d(i)x^{*}(i-k)This form can be expressed in terms of matrices :mathbf{R}_{x}(n),mathbf{w}_{n}=mathbf{r}_{dx}(n)where mathbf{R}_{x}(n) is the weighted
autocorrelation matrix for x(n) and mathbf{r}_{dx}(n) is thecross-correlation between d(n) and x(n). Based on this expression we find the coefficients which minimize the cost function as :mathbf{w}_{n}=mathbf{R}_{x}^{-1}(n),mathbf{r}_{dx}(n)This is the main result of the discussion.Choosing lambda
The smaller lambda is, the smaller contribution of previous samples. This makes the filter "more" sensitive to recent samples, which means more fluctuations in the filter co-efficients. The lambda=1 case is referred to as the "growing window RLS algorithm".
Recursive algorithm
The discussion resulted in a single equation to determine a coefficient vector which minimizes the cost function. In this section we want to derive a recursive solution of the form :mathbf{w}_{n}=mathbf{w}_{n-1}+Deltamathbf{w}_{n-1}where Deltamathbf{w}_{n-1} is a correction factor at time "n-1". We start the derivation of the recursive algorithm by expressing the cross correlation mathbf{r}_{dx}(n) in terms of mathbf{r}_{dx}(n-1) :The Woodbury matrix identity follows:Before we move on, it is necessary to bring mathbf{g}(n) into another form :The second step follows from the recursive definition of mathbf{r}_{dx}(n ). Next we incorporate the recursive definition of mathbf{P}(n) together with the alternate form of mathbf{g}(n) and get:
Note that the recursion for P follows a
Riccati equation and thus draws parallels to theKalman filter .ee also
*
Adaptive filter
*Least mean squares filter References
*
* Simon Haykin, "Adaptive Filter Theory", Prentice Hall, 2002, ISBN 0-13-048434-2
* M.H.A Davis, R.B. Vinter, "Stochastic Modelling and Control", Springer, 1985, ISBN 0-412-16200-8
Wikimedia Foundation. 2010.