Filter för minsta medelvärde

för minsta medelkvadrat ( LMS ) är en klass av adaptiva filter som används för att efterlikna ett önskat filter genom att hitta filterkoefficienterna som hänför sig till att producera den minsta medelkvadraten av felsignalen (skillnaden mellan den önskade och den faktiska signalen). Det är en stokastisk gradientsänkningsmetod genom att filtret endast anpassas baserat på felet vid den aktuella tidpunkten. Den uppfanns 1960 av Stanford University professor Bernard Widrow och hans första Ph.D. student, Ted Hoff .

Problemformulering

Relation till Wiener-filtret

Förverkligandet av kausal Wiener-filtret ser mycket ut som lösningen på minsta kvadraters uppskattning, förutom i signalbehandlingsdomänen. Minsta kvadratlösningen för inmatris $\mathbf {X}$ och utdatavektor ${\boldsymbol {y}}$ är

${\boldsymbol {\hat {\beta }}}=(\mathbf {X} ^{\mathbf {T} }\mathbf {X} )^{-1}\mathbf {X} ^{\mathbf {T} }{\boldsymbol {y}}.$

FIR-filtret med minsta medelkvadrat är relaterat till Wiener-filtret, men att minimera felkriteriet för det förra är inte beroende av korskorrelationer eller autokorrelationer. Dess lösning konvergerar till Wiener-filterlösningen. De flesta linjära adaptiva filtreringsproblem kan formuleras med hjälp av blockschemat ovan. Det vill säga ett okänt system $\mathbf {h} (n)$ ska identifieras och det adaptiva filtret försöker anpassa filtret ${\displaystyle {\hat {\mathbf { h} }}(n)} för att göra det så nära$$\mathbf {h} (n)$ som möjligt , samtidigt som man endast använder observerbara signaler $x(n)$ , $d(n)$ och $e(n)$ ; men $y(n)$ , $v(n)$ och $h(n)$ är inte direkt observerbara. Dess lösning är nära besläktad med Wiener-filtret .

Definition av symboler

$n$ är numret på det aktuella ingångsexemplet

$p$ är antalet filtertryck

$\{\cdot \}^{H}$ ( Hermitiskt transponera eller konjugerat transponera )

$\mathbf {x} (n)=\left[x(n) ,x(n-1),\dots ,x(np-1)\right]^{T}$

$\mathbf {h} (n)=\left[h_{0}(n),h_{1}(n),\dots ,h_{p-1 }(n)\right]^{T},\quad \mathbf {h} (n)\in \mathbb {C} ^{p}$

${ \displaystyle y(n)=\mathbf {h} ^{H}(n)\cdot \mathbf {x} (n)} d ( n ) = y$

$) )=y(n)+\nu (n)}$

${\hat {\mathbf {h} }}(n)$ uppskattat filter; tolka som uppskattningen av filterkoefficienterna efter n sampel

$e(n) =d(n)-{\hat {y}}(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\cdot \mathbf {x} (n)$

Aning

Grundidén bakom LMS-filtret är att närma sig de optimala filtervikterna ${\displaystyle (R^{-1}P)} ,$ genom att uppdatera filtervikterna på ett sätt så att de konvergerar till den optimala filtervikten. Detta är baserat på gradient descent-algoritmen. Algoritmen börjar med att anta små vikter (noll i de flesta fall) och, vid varje steg, genom att hitta gradienten för medelkvadratfelet uppdateras vikterna. Det vill säga, om MSE-gradienten är positiv, innebär det att felet skulle fortsätta att öka positivt om samma vikt används för ytterligare iterationer, vilket innebär att vi måste minska vikterna. På samma sätt, om gradienten är negativ, måste vi öka vikterna. Viktuppdateringsekvationen är

$W_{n+1}=W_{n}-\mu \nabla \varepsilon [n],$

där $\varepsilon$ representerar medelkvadratfelet och $\mu$ är en konvergenskoefficient.

Det negativa tecknet visar att vi går nedför felets lutning, $\varepsilon$ för att hitta filtervikterna, $W_{i}$ , som minimerar felet.

Medelkvadratfelet som funktion av filtervikter är en kvadratisk funktion vilket betyder att det bara har ett extremum, som minimerar medelkvadratfelet, vilket är den optimala vikten. LMS närmar sig således denna optimala vikt genom att stiga/sänka nedför kurvan för medelkvadratfel vs filtervikt.

Härledning

Tanken bakom LMS-filter är att använda den brantaste nedstigningen för att hitta filtervikter ${\hat {\mathbf {h} }}(n)$ som minimerar en kostnadsfunktion . Vi börjar med att definiera kostnadsfunktionen som

$C(n)=E\left\{|e(n)|^{2}\right\}$

där $e(n)$ är felet vid det aktuella provet n och $E\{\cdot \}$ anger det förväntade värdet .

Denna kostnadsfunktion ( $C(n)$ ) är medelkvadratfelet och den minimeras av LMS. Det är här som LMS har fått sitt namn. Att tillämpa den brantaste nedstigningen innebär att ta partiella derivator med avseende på de individuella ingångarna i filterkoefficientvektorn (vikt)

$\nabla _{{\hat {\mathbf {h} }}^{H}}C(n)=\nabla _{{\hat {\mathbf {h} }}^{H}}E\left\{e( n)\,e^{*}(n)\right\}=2E\left\{\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))\, e^{*}(n)\right\}$

där $\displaystyle \nabla }$ { är gradientoperatorn

$\nabla _{{\hat {\mathbf { h} }}^{H}}(e(n))=\nabla _{{\hat {\mathbf {h} }}^{H}}\left(d(n)-{\hat {\mathbf {h} }}^{H}\cdot \mathbf {x} (n)\right)=-\mathbf {x} (n)$

$\nabla C(n)=-2E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$

Nu är $\nabla C(n)$ en vektor som pekar mot kostnadsfunktionens brantaste stigning. För att hitta minimivärdet för kostnadsfunktionen måste vi ta ett steg i motsatt riktning av $\nabla C(n)$ . För att uttrycka det i matematiska termer

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)-{\frac {\mu }{2}}\nabla C(n)={\hat {\mathbf {h} }}(n)+\mu \,E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$

där ${\frac {\mu }{2}}$ är stegstorleken (anpassningskonstanten). Det betyder att vi har hittat en sekvensiell uppdateringsalgoritm som minimerar kostnadsfunktionen. Tyvärr är denna algoritm inte realiserbar förrän vi vet $E\left\{\mathbf {x} (n)\,e^{*}(n)\right \}$ .

I allmänhet beräknas inte förväntningarna ovan. För att köra LMS i en onlinemiljö (uppdatering efter varje nytt prov tas emot) använder vi istället en omedelbar uppskattning av den förväntningen. Se nedan.

Förenklingar

För de flesta system förväntas funktionen ${E}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}$ måste vara ungefärlig. Detta kan göras med följande opartiska skattare

${\hat {E}}\left\{\ mathbf {x} (n)\,e^{*}(n)\right\}={\frac {1}{N}}\summa _{i=0}^{N-1}\mathbf {x } (ni)\,e^{*}(ni)$

där $N$ indikerar antalet sampel vi använder för den uppskattningen. Det enklaste fallet är $N=1$

${\hat {E}}\left\{\mathbf {x} (n)\,e^{ *}(n)\right\}=\mathbf {x} (n)\,e^{*}(n)$

För det enkla fallet följer uppdateringsalgoritmen som

${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \mathbf {x} (n)\,e^{*}(n)$

Detta utgör faktiskt uppdateringsalgoritmen för LMS-filtret.

LMS-algoritmsammanfattning

LMS-algoritmen för ett ${\displaystyle p}:$ te ordningens filter kan sammanfattas som

Parametrar:	$p=$ filterordning
	$\mu =$ stegstorlek
Initiering:	${\hat {\mathbf {h} }}(0)=\operatörsnamn {nollor} (p)$
Beräkning:	För $n=0,1,2,...$
	$\mathbf {x} (n)=\left[x(n), x(n-1),\dots ,x(n-p+1)\right]^{T}$
	$e (n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)$
	${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \,e ^{*}(n)\mathbf {x} (n)$

Konvergens och stabilitet i medelvärdet

Eftersom LMS-algoritmen inte använder de exakta värdena på förväntningarna, skulle vikterna aldrig nå de optimala vikterna i absolut mening, men en konvergens är möjlig i medeltal. Det vill säga, även om vikterna kan ändras med små mängder, ändras det ungefär de optimala vikterna. Men om variansen med vilken vikterna ändras är stor, skulle konvergens i medelvärde vara missvisande. Detta problem kan uppstå om värdet för stegstorlek $\mu$ inte väljs korrekt.

Om $\mu$ väljs att vara stor, beror mängden med vilken vikterna ändras kraftigt på gradientuppskattningen, och därför kan vikterna ändras med ett stort värde så att gradienten som var negativ vid det första ögonblicket kan nu bli positiv. Och i det andra ögonblicket kan vikten ändras i motsatt riktning med en stor mängd på grund av den negativa gradienten och skulle således fortsätta att oscillera med en stor varians kring de optimala vikterna. Å andra sidan, om $\mu$ väljs för liten, blir tiden för att konvergera till de optimala vikterna för lång.

Således behövs en övre gräns på $\mu$ som ges som $0<\mu <{\frac {2}{\lambda _{\mathrm {max } }}}$

där $\lambda _{\max }$ är det största egenvärdet för autokorrelationsmatrisen $\mathbf {R} }=E\{ {\mathbf {x} }(n){\mathbf {x} ^{H}}(n)\}}$ { . Om detta villkor inte är uppfyllt blir algoritmen instabil och ${\hat {h}}(n)$ divergerar.

Maximal konvergenshastighet uppnås när

$\mu ={\frac {2}{\lambda _{\mathrm {max} }+\lambda _{\mathrm {min} }}},$

där $\lambda _{\min }$ är det minsta egenvärdet för ${\mathbf {R} }$ . Givet att $\mu$ är mindre än eller lika med detta optimum, bestäms konvergenshastigheten av ${\displaystyle \lambda _{\min }} ,$ med ett större värde som ger snabbare konvergens. Detta innebär att snabbare konvergens kan uppnås när $\lambda _{\max }$ är nära ${\displaystyle \lambda _{\min }} ,$ det vill säga den maximalt uppnåbara konvergenshastigheten beror på egenvärdesspridning av ${\mathbf {R} }$ .

En signal med vitt brus har autokorrelationsmatris ${\mathbf {R} }=\sigma ^{2}{\mathbf {I} }$ där $\sigma ^{2}$ är variansen för signalen. I detta fall är alla egenvärden lika, och egenvärdesspridningen är den minsta över alla möjliga matriser. Den vanliga tolkningen av detta resultat är därför att LMS konvergerar snabbt för vita insignaler och långsamt för färgade insignaler, såsom processer med lågpass- eller högpasskarakteristika.

Det är viktigt att notera att ovanstående övre gräns på $\mu$ endast framtvingar stabilitet i medelvärdet, men koefficienterna för ${\hat {h}}(n)$ kan fortfarande växa oändligt stor, dvs divergens av koefficienterna är fortfarande möjlig. En mer praktisk gräns är

$0<\mu <{\frac {2}{\mathrm {tr} \left[{\mathbf {R} }\right]}},$

där $\mathrm {tr} [{\mathbf {R} }]$ betecknar spåret av ${\mathbf {R} }$ . Denna gräns garanterar att koefficienterna för ${\hat {h}}(n)$ inte divergerar (i praktiken bör värdet på $\mu$ inte väljas nära detta övre gränsen, eftersom den är något optimistisk på grund av approximationer och antaganden som gjorts vid härledningen av gränsen).

Normaliserat minsta medelkvadratfilter (NLMS)

Den största nackdelen med den "rena" LMS-algoritmen är att den är känslig för skalningen av dess ingång $x(n)$ . Detta gör det mycket svårt (om inte omöjligt) att välja en inlärningshastighet $\mu$ som garanterar algoritmens stabilitet (Haykin 2002). Det normaliserade minsta medelkvadratfiltret (NLMS) är en variant av LMS-algoritmen som löser detta problem genom att normalisera med kraften från ingången. NLMS-algoritmen kan sammanfattas som:

Parametrar:	$p=$ filterordning
	$\mu =$ stegstorlek
Initiering:	${\hat {\mathbf {h} }}(0)=\operatörsnamn {nollor} (p)$
Beräkning:	För $n=0,1,2,...$
	$\mathbf {x} (n)=\left[x(n), x(n-1),\dots ,x(n-p+1)\right]^{T}$
	$e (n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)$
	${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }} (n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n) }}$

Optimal inlärningshastighet

Det kan visas att om det inte finns någon störning ( $v(n)=0$ ), så är den optimala inlärningshastigheten för NLMS-algoritmen

$\mu _{opt}=1$

och är oberoende av ingången $x(n)$ och det verkliga (okända) impulssvaret $\mathbf {h} (n)$ . I det allmänna fallet med störningar ( $v(n)\neq 0$ ), är den optimala inlärningshastigheten

$\mu _{opt}={\frac {E\left[\left|y(n)-{\hat {y}}(n)\right|^{2}\right]}{ E\vänster[|e(n)|^{2}\höger]}}$

Resultaten ovan antar att signalerna $v(n)$ och $x(n)$ är okorrelerade till varandra, vilket generellt är fallet i praktiken.

Bevis

Låt filterförskjutningen definieras som ${\displaystyle \Lambda (n)=\left|\mathbf {h} (n)-{\hat {\mathbf {h} }}(n)\right|^{2}} , vi kan härleda det$ förväntade feljustering för nästa prov som:

$E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \, e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\ höger|^{2}\höger]$

$E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \, \left(v^{*}(n)+y^{*}(n)-{\hat {y}}^{*}(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]$

Låt $\mathbf {\delta } ={\hat {\mathbf {h} }}(n)-\mathbf {h} (n)$ och $r(n)={\hat {y}}(n)-y(n)$

$E\left[\Lambda (n+1)\right]=E\left[\left|\mathbf {\delta} (n)-{\frac {\mu \,\left(v( n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right|^{2}\ höger]$

$E\left[\Lambda (n+1)\right]=E \left[\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\ mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left(\mathbf {\delta} (n)-{\frac {\mu \,\ vänster(v(n)+r(n)\höger)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\höger)\ höger]$

Förutsatt att vi är oberoende har vi:

$E\left[\Lambda (n+1)\right]=\Lambda (n)+E\left[\left({\frac {\mu \, \left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right) ^{H}\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}( n)\mathbf {x} (n)}}\right)\right]-2E\left[{\frac {\mu |r(n)|^{2}}{\mathbf {x} ^{H} (n)\mathbf {x} (n)}}\right]$

$E\left[\Lambda (n+1)\right]=\Lambda (n)+{\frac {\mu ^{2}E\left[| e(n)|^{2}\höger]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-{\frac {2\mu E\left[|r (n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}$

Den optimala inlärningshastigheten hittas vid ${\frac {dE\left[\Lambda (n+1)\right]}{d\mu }}=0$ , vilket leder till:

$2\mu E\left[|e(n)|^{2}\right]-2E\left[|r(n)|^{2}\right]=0$

$\mu ={\frac {E\left[|r(n)|^{2}\right]}{E\left[|e(n)|^{2}\right]}}$

Se även

• Rekursiva minsta kvadrater
• För statistiska tekniker som är relevanta för LMS-filtret, se Minsta kvadrater .
• Likheter mellan Wiener och LMS
• Multidelay block frekvensdomän adaptivt filter
• Nolltvingande equalizer
• Kernel adaptivt filter
• Matchat filter
• Wiener filter

•   Monson H. Hayes: Statistical Digital Signal Processing and Modeling, Wiley, 1996, ISBN 0-471-59431-8
•   Simon Haykin: Adaptive Filter Theory, Prentice Hall, 2002, ISBN 0-13-048434-2
•   Simon S. Haykin, Bernard Widrow (redaktör): Least-Mean-Square Adaptive Filters, Wiley, 2003, ISBN 0-471-21570-8
•   Bernard Widrow, Samuel D. Stearns: Adaptive Signal Processing, Prentice Hall, 1985, ISBN 0-13-004029-0
•   Weifeng Liu, Jose Principe och Simon Haykin: Kernel Adaptive Filtering: A Comprehensive Introduction, John Wiley, 2010, ISBN 0-470-44753-2
•   Paulo SR Diniz: Adaptiv filtrering: Algoritmer och praktisk implementering, Kluwer Academic Publishers, 1997, ISBN 0-7923-9912-9

externa länkar

• LMS-algoritm i adaptiva antennmatriser www.antenna-theory.com
• LMS Brusreducering demo www.advsolned.com