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 algorithm 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. x ( n ) = [ x ( n ) x ( n − 1 ) ⋮ x ( n − p ) ] {displaystyle mathbf {x} (n)=left} 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 algorithm 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 d ( n ) {displaystyle d(n)} is transmitted over an echoey, noisy channel that causes it to be received as where v ( n ) {displaystyle v(n)} represents additive noise. The intent of the RLS filter is to recover the desired signal d ( n ) {displaystyle d(n)} by use of a p + 1 {displaystyle p+1} -tap FIR filter, w {displaystyle mathbf {w} } : where x n = [ x ( n ) x ( n − 1 ) … x ( n − p ) ] T {displaystyle mathbf {x} _{n}=^{T}} is the column vector containing the p + 1 {displaystyle p+1} most recent samples of x ( n ) {displaystyle x(n)} . The estimate of the recovered desired signal is The goal is to estimate the parameters of the filter w {displaystyle mathbf {w} } , and at each time n {displaystyle n} we refer to the current estimate as w n {displaystyle mathbf {w} _{n}} and the adapted least-squares estimate by w n + 1 {displaystyle mathbf {w} _{n+1}} . w n {displaystyle mathbf {w} _{n}} is also a column vector, as shown below, and the transpose, w n T {displaystyle mathbf {w} _{n}^{mathit {T}}} , is a row vector. The matrix product w n T x n {displaystyle mathbf {w} _{n}^{mathit {T}}mathbf {x} _{n}} (which is the dot product of w n {displaystyle mathbf {w} _{n}} and x n {displaystyle mathbf {x} _{n}} ) is d ^ ( n ) {displaystyle {hat {d}}(n)} , a scalar. The estimate is 'good' if d ^ ( n ) − d ( n ) {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 w n + 1 {displaystyle mathbf {w} _{n+1}} , in terms of w n {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 C {displaystyle C} by appropriately selecting the filter coefficients w n {displaystyle mathbf {w} _{n}} , updating the filter as new data arrives. The error signal e ( n ) {displaystyle e(n)} and desired signal d ( n ) {displaystyle d(n)} are defined in the negative feedback diagram below: