Movatterモバイル変換


[0]ホーム

URL:


Jump to content
WikipediaThe Free Encyclopedia
Search

Recursive least squares filter

From Wikipedia, the free encyclopedia
Adaptive filter algorithm for digital signal processing

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

Motivation

[edit]

RLS was discovered byGauss 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 byadaptive filters. For example, suppose that a signald(n){\displaystyle d(n)} is transmitted over an echoey,noisy channel that causes it to be received as

x(n)=k=0qbn(k)d(nk)+v(n){\displaystyle x(n)=\sum _{k=0}^{q}b_{n}(k)d(n-k)+v(n)}

wherev(n){\displaystyle v(n)} representsadditive noise. The intent of the RLS filter is to recover the desired signald(n){\displaystyle d(n)} by use of ap+1{\displaystyle p+1}-tapFIR filter,w{\displaystyle \mathbf {w} }:

d(n)k=0pw(k)x(nk)=wTxn{\displaystyle d(n)\approx \sum _{k=0}^{p}w(k)x(n-k)=\mathbf {w} ^{\mathit {T}}\mathbf {x} _{n}}

wherexn=[x(n)x(n1)x(np)]T{\displaystyle \mathbf {x} _{n}=[x(n)\quad x(n-1)\quad \ldots \quad x(n-p)]^{T}} is thecolumn vector containing thep+1{\displaystyle p+1} most recent samples ofx(n){\displaystyle x(n)}. The estimate of the recovered desired signal is

d^(n)=k=0pwn(k)x(nk)=wnTxn{\displaystyle {\hat {d}}(n)=\sum _{k=0}^{p}w_{n}(k)x(n-k)=\mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}}

The goal is to estimate the parameters of the filterw{\displaystyle \mathbf {w} }, and at each timen{\displaystyle n} we refer to the current estimate aswn{\displaystyle \mathbf {w} _{n}} and the adapted least-squares estimate bywn+1{\displaystyle \mathbf {w} _{n+1}}.wn{\displaystyle \mathbf {w} _{n}} is also a column vector, as shown below, and thetranspose,wnT{\displaystyle \mathbf {w} _{n}^{\mathit {T}}}, is arow vector. Thematrix productwnTxn{\displaystyle \mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}} (which is thedot product ofwn{\displaystyle \mathbf {w} _{n}} andxn{\displaystyle \mathbf {x} _{n}}) isd^(n){\displaystyle {\hat {d}}(n)}, a scalar. The estimate is"good" ifd^(n)d(n){\displaystyle {\hat {d}}(n)-d(n)} is small in magnitude in someleast squares sense.

As time evolves, it is desired to avoid completely redoing the least squares algorithm to find the new estimate forwn+1{\displaystyle \mathbf {w} _{n+1}}, in terms ofwn{\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 theKalman filter.

Discussion

[edit]

The idea behind RLS filters is to minimize acost functionC{\displaystyle C} by appropriately selecting the filter coefficientswn{\displaystyle \mathbf {w} _{n}}, updating the filter as new data arrives. The error signale(n){\displaystyle e(n)} and desired signald(n){\displaystyle d(n)} are defined in thenegative feedback diagram below:

The error implicitly depends on the filter coefficients through the estimated^(n){\displaystyle {\hat {d}}(n)}:

e(n)=d(n)d^(n){\displaystyle e(n)=d(n)-{\hat {d}}(n)}

The weighted least squares error functionC{\displaystyle C}—the cost function we desire to minimize—being a function ofe(n){\displaystyle e(n)} is therefore also dependent on the filter coefficients:

C(wn)=i=0nλnie2(i){\displaystyle C(\mathbf {w} _{n})=\sum _{i=0}^{n}\lambda ^{n-i}e^{2}(i)}

where0<λ1{\displaystyle 0<\lambda \leq 1} is the "forgetting factor" which gives exponentially less weight to older error samples.

The cost function is minimized by taking the partial derivatives for all entriesk{\displaystyle k} of the coefficient vectorwn{\displaystyle \mathbf {w} _{n}} and setting the results to zero

C(wn)wn(k)=i=0n2λnie(i)e(i)wn(k)=i=0n2λnie(i)x(ik)=0k=0,1,,p{\displaystyle {\frac {\partial C(\mathbf {w} _{n})}{\partial w_{n}(k)}}=\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\cdot {\frac {\partial e(i)}{\partial w_{n}(k)}}=-\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\,x(i-k)=0\qquad k=0,1,\ldots ,p}

Next, replacee(n){\displaystyle e(n)} with the definition of the error signal

i=0nλni[d(i)=0pwn()x(i)]x(ik)=0k=0,1,,p{\displaystyle \sum _{i=0}^{n}\lambda ^{n-i}\left[d(i)-\sum _{\ell =0}^{p}w_{n}(\ell )x(i-\ell )\right]x(i-k)=0\qquad k=0,1,\ldots ,p}

Rearranging the equation yields

=0pwn()[i=0nλnix(i)x(ik)]=i=0nλnid(i)x(ik)k=0,1,,p{\displaystyle \sum _{\ell =0}^{p}w_{n}(\ell )\left[\sum _{i=0}^{n}\lambda ^{n-i}\,x(i-\ell )x(i-k)\right]=\sum _{i=0}^{n}\lambda ^{n-i}d(i)x(i-k)\qquad k=0,1,\ldots ,p}

This form can be expressed in terms of matrices

Rx(n)wn=rdx(n){\displaystyle \mathbf {R} _{x}(n)\,\mathbf {w} _{n}=\mathbf {r} _{dx}(n)}

whereRx(n){\displaystyle \mathbf {R} _{x}(n)} is the weightedsample covariance matrix forx(n){\displaystyle x(n)}, andrdx(n){\displaystyle \mathbf {r} _{dx}(n)} is the equivalent estimate for thecross-covariance betweend(n){\displaystyle d(n)} andx(n){\displaystyle x(n)}. Based on this expression we find the coefficients which minimize the cost function as

wn=Rx1(n)rdx(n){\displaystyle \mathbf {w} _{n}=\mathbf {R} _{x}^{-1}(n)\,\mathbf {r} _{dx}(n)}

This is the main result of the discussion.

Choosing λ

[edit]

The smallerλ{\displaystyle \lambda } is, the smaller is the contribution of previous samples to thecovariance matrix. This makes the filtermore sensitive to recent samples, which means more fluctuations in the filter co-efficients. Theλ=1{\displaystyle \lambda =1} case is referred to as thegrowing window RLS algorithm. In practice,λ{\displaystyle \lambda } is usually chosen between 0.98 and 1.[1] By using type-IImaximum likelihood estimation the optimalλ{\displaystyle \lambda } can be estimated from a set of data.[2]

Recursive algorithm

[edit]

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

wn=wn1+Δwn1{\displaystyle \mathbf {w} _{n}=\mathbf {w} _{n-1}+\Delta \mathbf {w} _{n-1}}

whereΔwn1{\displaystyle \Delta \mathbf {w} _{n-1}} is a correction factor at timen1{\displaystyle {n-1}}. We start the derivation of the recursive algorithm by expressing the cross covariancerdx(n){\displaystyle \mathbf {r} _{dx}(n)} in terms ofrdx(n1){\displaystyle \mathbf {r} _{dx}(n-1)}

rdx(n){\displaystyle \mathbf {r} _{dx}(n)}=i=0nλnid(i)x(i){\displaystyle =\sum _{i=0}^{n}\lambda ^{n-i}d(i)\mathbf {x} (i)}
=i=0n1λnid(i)x(i)+λ0d(n)x(n){\displaystyle =\sum _{i=0}^{n-1}\lambda ^{n-i}d(i)\mathbf {x} (i)+\lambda ^{0}d(n)\mathbf {x} (n)}
=λrdx(n1)+d(n)x(n){\displaystyle =\lambda \mathbf {r} _{dx}(n-1)+d(n)\mathbf {x} (n)}

wherex(i){\displaystyle \mathbf {x} (i)} is thep+1{\displaystyle {p+1}} dimensional data vector

x(i)=[x(i),x(i1),,x(ip)]T{\displaystyle \mathbf {x} (i)=[x(i),x(i-1),\dots ,x(i-p)]^{T}}

Similarly we expressRx(n){\displaystyle \mathbf {R} _{x}(n)} in terms ofRx(n1){\displaystyle \mathbf {R} _{x}(n-1)} by

Rx(n){\displaystyle \mathbf {R} _{x}(n)}=i=0nλnix(i)xT(i){\displaystyle =\sum _{i=0}^{n}\lambda ^{n-i}\mathbf {x} (i)\mathbf {x} ^{T}(i)}
=λRx(n1)+x(n)xT(n){\displaystyle =\lambda \mathbf {R} _{x}(n-1)+\mathbf {x} (n)\mathbf {x} ^{T}(n)}

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

A{\displaystyle A}=λRx(n1){\displaystyle =\lambda \mathbf {R} _{x}(n-1)} is(p+1){\displaystyle (p+1)}-by-(p+1){\displaystyle (p+1)}
U{\displaystyle U}=x(n){\displaystyle =\mathbf {x} (n)} is(p+1){\displaystyle (p+1)}-by-1 (column vector)
V{\displaystyle V}=xT(n){\displaystyle =\mathbf {x} ^{T}(n)} is 1-by-(p+1){\displaystyle (p+1)} (row vector)
C{\displaystyle C}=I1{\displaystyle =\mathbf {I} _{1}} is the 1-by-1identity matrix

The Woodbury matrix identity follows

Rx1(n){\displaystyle \mathbf {R} _{x}^{-1}(n)}={\displaystyle =}[λRx(n1)+x(n)xT(n)]1{\displaystyle \left[\lambda \mathbf {R} _{x}(n-1)+\mathbf {x} (n)\mathbf {x} ^{T}(n)\right]^{-1}}
={\displaystyle =}1λ{Rx1(n1)Rx1(n1)x(n)xT(n)Rx1(n1)λ+xT(n)Rx1(n1)x(n)}{\displaystyle {\dfrac {1}{\lambda }}\left\lbrace \mathbf {R} _{x}^{-1}(n-1)-{\dfrac {\mathbf {R} _{x}^{-1}(n-1)\mathbf {x} (n)\mathbf {x} ^{T}(n)\mathbf {R} _{x}^{-1}(n-1)}{\lambda +\mathbf {x} ^{T}(n)\mathbf {R} _{x}^{-1}(n-1)\mathbf {x} (n)}}\right\rbrace }
{\displaystyle }

To come in line with the standard literature, we define

P(n){\displaystyle \mathbf {P} (n)}=Rx1(n){\displaystyle =\mathbf {R} _{x}^{-1}(n)}
=λ1P(n1)g(n)xT(n)λ1P(n1){\displaystyle =\lambda ^{-1}\mathbf {P} (n-1)-\mathbf {g} (n)\mathbf {x} ^{T}(n)\lambda ^{-1}\mathbf {P} (n-1)}

where thegain vectorg(n){\displaystyle g(n)} is

g(n){\displaystyle \mathbf {g} (n)}=λ1P(n1)x(n){1+xT(n)λ1P(n1)x(n)}1{\displaystyle =\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)\left\{1+\mathbf {x} ^{T}(n)\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)\right\}^{-1}}
=P(n1)x(n){λ+xT(n)P(n1)x(n)}1{\displaystyle =\mathbf {P} (n-1)\mathbf {x} (n)\left\{\lambda +\mathbf {x} ^{T}(n)\mathbf {P} (n-1)\mathbf {x} (n)\right\}^{-1}}

Before we move on, it is necessary to bringg(n){\displaystyle \mathbf {g} (n)} into another form

g(n){1+xT(n)λ1P(n1)x(n)}{\displaystyle \mathbf {g} (n)\left\{1+\mathbf {x} ^{T}(n)\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)\right\}}=λ1P(n1)x(n){\displaystyle =\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)}
g(n)+g(n)xT(n)λ1P(n1)x(n){\displaystyle \mathbf {g} (n)+\mathbf {g} (n)\mathbf {x} ^{T}(n)\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)}=λ1P(n1)x(n){\displaystyle =\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)}

Subtracting the second term on the left side yields

g(n){\displaystyle \mathbf {g} (n)}=λ1P(n1)x(n)g(n)xT(n)λ1P(n1)x(n){\displaystyle =\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)-\mathbf {g} (n)\mathbf {x} ^{T}(n)\lambda ^{-1}\mathbf {P} (n-1)\mathbf {x} (n)}
=λ1[P(n1)g(n)xT(n)P(n1)]x(n){\displaystyle =\lambda ^{-1}\left[\mathbf {P} (n-1)-\mathbf {g} (n)\mathbf {x} ^{T}(n)\mathbf {P} (n-1)\right]\mathbf {x} (n)}

With therecursive definition ofP(n){\displaystyle \mathbf {P} (n)} the desired form follows

g(n)=P(n)x(n){\displaystyle \mathbf {g} (n)=\mathbf {P} (n)\mathbf {x} (n)}

Now we are ready to complete the recursion. As discussed

wn{\displaystyle \mathbf {w} _{n}}=P(n)rdx(n){\displaystyle =\mathbf {P} (n)\,\mathbf {r} _{dx}(n)}
=λP(n)rdx(n1)+d(n)P(n)x(n){\displaystyle =\lambda \mathbf {P} (n)\,\mathbf {r} _{dx}(n-1)+d(n)\mathbf {P} (n)\,\mathbf {x} (n)}

The second step follows from the recursive definition ofrdx(n){\displaystyle \mathbf {r} _{dx}(n)}. Next we incorporate the recursive definition ofP(n){\displaystyle \mathbf {P} (n)} together with the alternate form ofg(n){\displaystyle \mathbf {g} (n)} and get

wn{\displaystyle \mathbf {w} _{n}}=λ[λ1P(n1)g(n)xT(n)λ1P(n1)]rdx(n1)+d(n)g(n){\displaystyle =\lambda \left[\lambda ^{-1}\mathbf {P} (n-1)-\mathbf {g} (n)\mathbf {x} ^{T}(n)\lambda ^{-1}\mathbf {P} (n-1)\right]\mathbf {r} _{dx}(n-1)+d(n)\mathbf {g} (n)}
=P(n1)rdx(n1)g(n)xT(n)P(n1)rdx(n1)+d(n)g(n){\displaystyle =\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)-\mathbf {g} (n)\mathbf {x} ^{T}(n)\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)+d(n)\mathbf {g} (n)}
=P(n1)rdx(n1)+g(n)[d(n)xT(n)P(n1)rdx(n1)]{\displaystyle =\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)+\mathbf {g} (n)\left[d(n)-\mathbf {x} ^{T}(n)\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)\right]}

Withwn1=P(n1)rdx(n1){\displaystyle \mathbf {w} _{n-1}=\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)} we arrive at the update equation

wn{\displaystyle \mathbf {w} _{n}}=wn1+g(n)[d(n)xT(n)wn1]{\displaystyle =\mathbf {w} _{n-1}+\mathbf {g} (n)\left[d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n-1}\right]}
=wn1+g(n)α(n){\displaystyle =\mathbf {w} _{n-1}+\mathbf {g} (n)\alpha (n)}

whereα(n)=d(n)xT(n)wn1{\displaystyle \alpha (n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n-1}}is thea priori error. Compare this with thea posteriori error; the error calculatedafter the filter is updated:

e(n)=d(n)xT(n)wn{\displaystyle e(n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n}}

That means we found the correction factor

Δwn1=g(n)α(n){\displaystyle \Delta \mathbf {w} _{n-1}=\mathbf {g} (n)\alpha (n)}

This intuitively satisfying result indicates that the correction factor is directly proportional to both the error and the gain vector, which controls how much sensitivity is desired, through the weighting factor,λ{\displaystyle \lambda }.

RLS algorithm summary

[edit]

The RLS algorithm for ap-th order RLS filter can be summarized as

Parameters:p={\displaystyle p=} filter order
λ={\displaystyle \lambda =} forgetting factor
δ={\displaystyle \delta =} value to initializeP(0){\displaystyle \mathbf {P} (0)}
Initialization:w(0)=0{\displaystyle \mathbf {w} (0)=0},
x(k)=0,k=p,,1{\displaystyle x(k)=0,k=-p,\dots ,-1},
d(k)=0,k=p,,1{\displaystyle d(k)=0,k=-p,\dots ,-1}
P(0)=δI{\displaystyle \mathbf {P} (0)=\delta I} whereI{\displaystyle I} is theidentity matrix of rankp+1{\displaystyle p+1}
Computation:Forn=1,2,{\displaystyle n=1,2,\dots }

x(n)=[x(n)x(n1)x(np)]{\displaystyle \mathbf {x} (n)=\left[{\begin{matrix}x(n)\\x(n-1)\\\vdots \\x(n-p)\end{matrix}}\right]}

α(n)=d(n)xT(n)w(n1){\displaystyle \alpha (n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} (n-1)}
g(n)=P(n1)x(n){λ+xT(n)P(n1)x(n)}1{\displaystyle \mathbf {g} (n)=\mathbf {P} (n-1)\mathbf {x} (n)\left\{\lambda +\mathbf {x} ^{T}(n)\mathbf {P} (n-1)\mathbf {x} (n)\right\}^{-1}}
P(n)=λ1P(n1)g(n)xT(n)λ1P(n1){\displaystyle \mathbf {P} (n)=\lambda ^{-1}\mathbf {P} (n-1)-\mathbf {g} (n)\mathbf {x} ^{T}(n)\lambda ^{-1}\mathbf {P} (n-1)}
w(n)=w(n1)+α(n)g(n){\displaystyle \mathbf {w} (n)=\mathbf {w} (n-1)+\,\alpha (n)\mathbf {g} (n)}.

The recursion forP{\displaystyle P} follows analgebraic Riccati equation and thus draws parallels to theKalman filter.[3]

Lattice recursive least squares filter (LRLS)

[edit]

Thelattice recursive least squaresadaptive filter is related to the standard RLS except that it requires fewer arithmetic operations (orderN).[4] 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 ona posteriori errors and includes the normalized form. The derivation is similar to the standard RLS algorithm and is based on the definition ofd(k){\displaystyle d(k)\,\!}. In the forward prediction case, we haved(k)=x(k){\displaystyle d(k)=x(k)\,\!} with the input signalx(k1){\displaystyle x(k-1)\,\!} as the most up to date sample. The backward prediction case isd(k)=x(ki1){\displaystyle d(k)=x(k-i-1)\,\!}, where i is the index of the sample in the past we want to predict, and the input signalx(k){\displaystyle x(k)\,\!} is the most recent sample.[5]

Parameter summary

[edit]
κf(k,i){\displaystyle \kappa _{f}(k,i)\,\!} is the forward reflection coefficient
κb(k,i){\displaystyle \kappa _{b}(k,i)\,\!} is the backward reflection coefficient
ef(k,i){\displaystyle e_{f}(k,i)\,\!} represents the instantaneousa posteriori forward prediction error
eb(k,i){\displaystyle e_{b}(k,i)\,\!} represents the instantaneousa posteriori backward prediction error
ξbmind(k,i){\displaystyle \xi _{b_{\min }}^{d}(k,i)\,\!} is the minimum least-squares backward prediction error
ξfmind(k,i){\displaystyle \xi _{f_{\min }}^{d}(k,i)\,\!} is the minimum least-squares forward prediction error
γ(k,i){\displaystyle \gamma (k,i)\,\!} is a conversion factor betweena priori anda posteriori errors
vi(k){\displaystyle v_{i}(k)\,\!} are the feedforward multiplier coefficients.
ε{\displaystyle \varepsilon \,\!} is a small positive constant that can be 0.01

LRLS algorithm summary

[edit]

The algorithm for a LRLS filter can be summarized as

Initialization:
Fori=0,1,,N{\textstyle i=0,1,\ldots ,N}
 δ(1,i)=δD(1,i)=0{\displaystyle \delta (-1,i)=\delta _{D}(-1,i)=0\,\!} (ifx(k)=0{\textstyle x(k)=0} fork<0{\textstyle k<0})
 ξbmind(1,i)=ξfmind(1,i)=ε{\displaystyle \xi _{b_{\min }}^{d}(-1,i)=\xi _{f_{\min }}^{d}(-1,i)=\varepsilon }
 γ(1,i)=1{\displaystyle \gamma (-1,i)=1\,\!}
 eb(1,i)=0{\displaystyle e_{b}(-1,i)=0\,\!}
End
Computation:
Fork0{\textstyle k\geq 0}
 γ(k,0)=1{\displaystyle \gamma (k,0)=1\,\!}
 eb(k,0)=ef(k,0)=x(k){\displaystyle e_{b}(k,0)=e_{f}(k,0)=x(k)\,\!}
 ξbmind(k,0)=ξfmind(k,0)=x2(k)+λξfmind(k1,0){\displaystyle \xi _{b_{\min }}^{d}(k,0)=\xi _{f_{\min }}^{d}(k,0)=x^{2}(k)+\lambda \xi _{f_{\min }}^{d}(k-1,0)\,\!}
 e(k,0)=d(k){\displaystyle e(k,0)=d(k)\,\!}
 Fori=0,1,,N{\textstyle i=0,1,\ldots ,N}
 δ(k,i)=λδ(k1,i)+eb(k1,i)ef(k,i)γ(k1,i){\displaystyle \delta (k,i)=\lambda \delta (k-1,i)+{\frac {e_{b}(k-1,i)e_{f}(k,i)}{\gamma (k-1,i)}}}
 γ(k,i+1)=γ(k,i)eb2(k,i)ξbmind(k,i){\displaystyle \gamma (k,i+1)=\gamma (k,i)-{\frac {e_{b}^{2}(k,i)}{\xi _{b_{\min }}^{d}(k,i)}}}
 κb(k,i)=δ(k,i)ξfmind(k,i){\displaystyle \kappa _{b}(k,i)={\frac {\delta (k,i)}{\xi _{f_{\min }}^{d}(k,i)}}}
 κf(k,i)=δ(k,i)ξbmind(k1,i){\displaystyle \kappa _{f}(k,i)={\frac {\delta (k,i)}{\xi _{b_{\min }}^{d}(k-1,i)}}}
 eb(k,i+1)=eb(k1,i)κb(k,i)ef(k,i){\displaystyle e_{b}(k,i+1)=e_{b}(k-1,i)-\kappa _{b}(k,i)e_{f}(k,i)\,\!}
 ef(k,i+1)=ef(k,i)κf(k,i)eb(k1,i){\displaystyle e_{f}(k,i+1)=e_{f}(k,i)-\kappa _{f}(k,i)e_{b}(k-1,i)\,\!}
 ξbmind(k,i+1)=ξbmind(k1,i)δ(k,i)κb(k,i){\displaystyle \xi _{b_{\min }}^{d}(k,i+1)=\xi _{b_{\min }}^{d}(k-1,i)-\delta (k,i)\kappa _{b}(k,i)}
 ξfmind(k,i+1)=ξfmind(k,i)δ(k,i)κf(k,i){\displaystyle \xi _{f_{\min }}^{d}(k,i+1)=\xi _{f_{\min }}^{d}(k,i)-\delta (k,i)\kappa _{f}(k,i)}
 Feedforward filtering
 δD(k,i)=λδD(k1,i)+e(k,i)eb(k,i)γ(k,i){\displaystyle \delta _{D}(k,i)=\lambda \delta _{D}(k-1,i)+{\frac {e(k,i)e_{b}(k,i)}{\gamma (k,i)}}}
 vi(k)=δD(k,i)ξbmind(k,i){\displaystyle v_{i}(k)={\frac {\delta _{D}(k,i)}{\xi _{b_{\min }}^{d}(k,i)}}}
 e(k,i+1)=e(k,i)vi(k)eb(k,i){\displaystyle e(k,i+1)=e(k,i)-v_{i}(k)e_{b}(k,i)\,\!}
 End
End

Normalized lattice recursive least squares filter (NLRLS)

[edit]

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

[edit]

The algorithm for a NLRLS filter can be summarized as

Initialization:
Fori=0,1,,N.{\textstyle i=0,1,\ldots ,N.}
 δ¯(1,i)=0{\displaystyle {\overline {\delta }}(-1,i)=0\,\!} (ifx(k)=d(k)=0{\textstyle x(k)=d(k)=0} fork<0{\textstyle k<0})
 δ¯D(1,i)=0{\displaystyle {\overline {\delta }}_{D}(-1,i)=0\,\!}
 e¯b(1,i)=0{\displaystyle {\overline {e}}_{b}(-1,i)=0\,\!}
End
 σx2(1)=λσd2(1)=ε{\displaystyle \sigma _{x}^{2}(-1)=\lambda \sigma _{d}^{2}(-1)=\varepsilon \,\!}
Computation:
Fork0{\textstyle k\geq 0}
 σx2(k)=λσx2(k1)+x2(k){\displaystyle \sigma _{x}^{2}(k)=\lambda \sigma _{x}^{2}(k-1)+x^{2}(k)\,\!} (Input signal energy)
 σd2(k)=λσd2(k1)+d2(k){\displaystyle \sigma _{d}^{2}(k)=\lambda \sigma _{d}^{2}(k-1)+d^{2}(k)\,\!} (Reference signal energy)
 e¯b(k,0)=e¯f(k,0)=x(k)σx(k){\displaystyle {\overline {e}}_{b}(k,0)={\overline {e}}_{f}(k,0)={\frac {x(k)}{\sigma _{x}(k)}}\,\!}
 e¯(k,0)=d(k)σd(k){\displaystyle {\overline {e}}(k,0)={\frac {d(k)}{\sigma _{d}(k)}}\,\!}
 Fori=0,1,,N{\textstyle i=0,1,\ldots ,N}
 δ¯(k,i)=δ(k1,i)(1e¯b2(k1,i))(1e¯f2(k,i))+e¯b(k1,i)e¯f(k,i){\displaystyle {\overline {\delta }}(k,i)=\delta (k-1,i){\sqrt {(1-{\overline {e}}_{b}^{2}(k-1,i))(1-{\overline {e}}_{f}^{2}(k,i))}}+{\overline {e}}_{b}(k-1,i){\overline {e}}_{f}(k,i)}
 e¯b(k,i+1)=e¯b(k1,i)δ¯(k,i)e¯f(k,i)(1δ¯2(k,i))(1e¯f2(k,i)){\displaystyle {\overline {e}}_{b}(k,i+1)={\frac {{\overline {e}}_{b}(k-1,i)-{\overline {\delta }}(k,i){\overline {e}}_{f}(k,i)}{\sqrt {(1-{\overline {\delta }}^{2}(k,i))(1-{\overline {e}}_{f}^{2}(k,i))}}}}
 e¯f(k,i+1)=e¯f(k,i)δ¯(k,i)e¯b(k1,i)(1δ¯2(k,i))(1e¯b2(k1,i)){\displaystyle {\overline {e}}_{f}(k,i+1)={\frac {{\overline {e}}_{f}(k,i)-{\overline {\delta }}(k,i){\overline {e}}_{b}(k-1,i)}{\sqrt {(1-{\overline {\delta }}^{2}(k,i))(1-{\overline {e}}_{b}^{2}(k-1,i))}}}}
 Feedforward filter
 δ¯D(k,i)=δ¯D(k1,i)(1e¯b2(k,i))(1e¯2(k,i))+e¯(k,i)e¯b(k,i){\displaystyle {\overline {\delta }}_{D}(k,i)={\overline {\delta }}_{D}(k-1,i){\sqrt {(1-{\overline {e}}_{b}^{2}(k,i))(1-{\overline {e}}^{2}(k,i))}}+{\overline {e}}(k,i){\overline {e}}_{b}(k,i)}
 e¯(k,i+1)=1(1e¯b2(k,i))(1δ¯D2(k,i))[e¯(k,i)δ¯D(k,i)e¯b(k,i)]{\displaystyle {\overline {e}}(k,i+1)={\frac {1}{\sqrt {(1-{\overline {e}}_{b}^{2}(k,i))(1-{\overline {\delta }}_{D}^{2}(k,i))}}}[{\overline {e}}(k,i)-{\overline {\delta }}_{D}(k,i){\overline {e}}_{b}(k,i)]}
 End
End

See also

[edit]

References

[edit]
  • Hayes, Monson H. (1996). "9.4: Recursive Least Squares".Statistical Digital Signal Processing and Modeling. Wiley. p. 541.ISBN 0-471-59431-8.
  • 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
  • Weifeng Liu, Jose Principe and Simon Haykin,Kernel Adaptive Filtering: A Comprehensive Introduction, John Wiley, 2010,ISBN 0-470-44753-2
  • R.L.Plackett,Some Theorems in Least Squares, Biometrika, 1950, 37, 149–157,ISSN 0006-3444
  • C.F.Gauss,Theoria combinationis observationum erroribus minimis obnoxiae, 1821, Werke, 4. Gottinge

Notes

[edit]
  1. ^Emannual C. Ifeacor, Barrie W. Jervis. Digital signal processing: a practical approach, second edition. Indianapolis: Pearson Education Limited, 2002, p. 718
  2. ^Steven Van Vaerenbergh, Ignacio Santamaría, Miguel Lázaro-Gredilla"Estimation of the forgetting factor in kernel recursive least squares", 2012 IEEE International Workshop on Machine Learning for Signal Processing, 2012, accessed June 23, 2016.
  3. ^Welch, Greg and Bishop, Gary"An Introduction to the Kalman Filter", Department of Computer Science, University of North Carolina at Chapel Hill, September 17, 1997, accessed July 19, 2011.
  4. ^Diniz, Paulo S.R., "Adaptive Filtering: Algorithms and Practical Implementation", Springer Nature Switzerland AG 2020, Chapter 7: Adaptive Lattice-Based RLS Algorithms.https://doi.org/10.1007/978-3-030-29057-3_7
  5. ^Albu, Kadlec, Softley, Matousek, Hermanek, Coleman, Fagan"Implementation of (Normalised) RLS Lattice on Virtex"Archived 2016-03-04 at theWayback Machine, Digital Signal Processing, 2001, accessed December 24, 2011.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Recursive_least_squares_filter&oldid=1325957194"
Categories:
Hidden categories:

[8]ページ先頭

©2009-2026 Movatter.jp