Recursive least squares filter on arvau

Wikipedia / 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.

Motivation

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 is transmitted over an echoey, noisy channel that causes it to be received as

represents additive noise-tap FIR:

is the column vector. The estimate of the recovered desired signal is

is also a column vector, as shown below, and the transpose, is a row vector. The matrix product (which is the dot product, a scalar. The estimate is "good" is small in magnitude in some least squares sense.

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.

Discussion

The idea behind RLS filters is to minimize a cost function are defined in the negative feedback diagram below:

is therefore also dependent on the filter coefficients:

is the "forgetting factor" which gives exponentially less weight to older error samples.

and setting the results to zero

with the definition of the error signal

Rearranging the equation yields

This form can be expressed in terms of matrices

is the weighted sample covariance is the equivalent estimate for the cross-covariance. Based on this expression we find the coefficients which minimize the cost function as

This is the main result of the discussion.

Choosing λ

is, the smaller is the contribution of previous samples to the covariance matrix. This makes the filter more case is referred to as the growing window RLS algorithm is usually chosen between 0.98 and 1. By using type-II maximum likelihood estimation can be estimated from a set of data.

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

dimensional data vector

|} In order to generate the coefficient vector we are interested in the inverse of the deterministic auto-covariance matrix. For that task the Woodbury matrix identity comes in handy. With

is the 1-by-1 identity matrix |} The Woodbury matrix identity follows

|} To come in line with the standard literature, we define

|} where the gain vector is

into another form

|} Subtracting the second term on the left side yields

|} With the recursive definition the desired form follows

Now we are ready to complete the recursion. As discussed

and get

we arrive at the update equation

is the a priori error. Compare this with the a posteriori error; the error calculated after the filter is updated:

That means we found the correction factor

RLS algorithm summary

The RLS algorithm for a p-th order RLS filter can be summarized as follows an algebraic Riccati equation and thus draws parallels to the Kalman filter.

Lattice recursive least squares filter (LRLS)

The lattice recursive least squares adaptive filter is related to the standard RLS except that it requires fewer arithmetic operations (order N). It offers additional advantages over conventional LMS algorithms such as faster convergence rates, modular structure, and insensitivity to variations in eigenvalue spread of the input correlation matrix. The LRLS algorithm described is based on a posteriori is the most recent sample.

Parameter summary

is the forward reflection coefficient
is the backward reflection coefficient
represents the instantaneous a posteriori forward prediction error
represents the instantaneous a posteriori backward prediction error
is the minimum least-squares backward prediction error
is the minimum least-squares forward prediction error
is a conversion factor between a priori and a posteriori errors
are the feedforward multiplier coefficients.
is a small positive constant that can be 0.01

LRLS algorithm summary

The algorithm for a LRLS filter can be summarized as

Normalized lattice recursive least squares filter (NLRLS)

The normalized form of the LRLS has fewer recursions and variables. It can be calculated by applying a normalization to the internal variables of the algorithm which will keep their magnitude bounded by one. This is generally not used in real-time applications because of the number of division and square-root operations which comes with a high computational load.

NLRLS algorithm summary

The algorithm for a NLRLS filter can be summarized as

References

Simon Haykin, Adaptive Filter Theory, Prentice Hall, 2002,
M.H.A Davis, R.B. Vinter, Stochastic Modelling and Control, Springer, 1985,
Weifeng Liu, Jose Principe and Simon Haykin, Kernel Adaptive Filtering: A Comprehensive Introduction, John Wiley, 2010,
R.L.Plackett, Some Theorems in Least Squares, Biometrika, 1950, 37, 149–157,
C.F.Gauss, Theoria combinationis observationum erroribus minimis obnoxiae, 1821, Werke, 4. Gottinge