Nejméně střední filtr čtverců - Least mean squares filter

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Ledna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Nejméně střední čtverce (LMS) Algoritmy jsou třídou adaptivní filtr slouží k napodobení požadovaného filtru vyhledáním koeficientů filtru, které souvisejí s produkcí nejmenší střední kvadratury chybového signálu (rozdíl mezi požadovaným a skutečným signálem). Je to stochastický gradient metoda v tom, že filtr je přizpůsoben pouze na základě chyby v aktuálním čase. To bylo vynalezeno v roce 1960 Stanfordská Univerzita profesor Bernard Widrow a jeho první Ph.D. student, Ted Hoff.

Formulace problému

Vztah k Wienerovu filtru

Realizace příčinné souvislosti Wienerův filtr vypadá hodně jako řešení odhadu nejmenších čtverců, s výjimkou domény zpracování signálu. Řešení nejmenších čtverců pro vstupní matici ${ displaystyle mathbf {X}}$ a výstupní vektor ${ displaystyle { boldsymbol {y}}}$je

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

Filtr nejmenších středních čtverců FIR souvisí s Wienerovým filtrem, ale minimalizace chybového kritéria prvního se nespoléhá na vzájemné korelace nebo automatické korelace. Jeho řešení konverguje k řešení Wienerova filtru. Většinu problémů s lineárním adaptivním filtrováním lze formulovat pomocí blokového diagramu výše. To znamená neznámý systém ${ displaystyle mathbf {h} (n)}$ je třeba identifikovat a adaptivní filtr se pokusí upravit filtr ${ displaystyle { hat { mathbf {h}}} (n)}$ aby to bylo co nejblíže ${ displaystyle mathbf {h} (n)}$, při použití pouze pozorovatelných signálů ${ displaystyle x (n)}$, ${ displaystyle d (n)}$ a ${ displaystyle e (n)}$; ale ${ displaystyle y (n)}$, ${ displaystyle v (n)}$ a ${ displaystyle h (n)}$ nejsou přímo pozorovatelné. Jeho řešení úzce souvisí s Wienerův filtr.

Definice symbolů

${ displaystyle n}$ je číslo aktuálního vstupního vzorku

${ displaystyle p}$ je počet odboček filtru

${ displaystyle { cdot } ^ {H}}$ (Hermitian transponovat nebo konjugovat transponovat )

${ displaystyle mathbf {x} (n) = doleva [x (n), x (n-1), tečky, x (n-p + 1) doprava] ^ {T}}$

${ displaystyle 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)}$

${ displaystyle d (n) = y (n) + nu (n)}$

${ displaystyle { hat { mathbf {h}}} (n)}$ odhadovaný filtr; interpretovat jako odhad filtračních koeficientů po n Vzorky

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

Idea

Základní myšlenkou LMS filtru je přiblížit se k optimální hmotnosti filtru ${ displaystyle (R ^ {- 1} P)}$aktualizací hmotností filtru tak, aby konvergoval k optimální hmotnosti filtru. To je založeno na algoritmu gradientního sestupu. Algoritmus začíná předpokládáním malých vah (ve většině případů nula) a v každém kroku nalezením gradientu střední kvadratické chyby se váhy aktualizují. To znamená, že pokud je gradient MSE pozitivní, znamená to, že by chyba neustále se zvyšujte pozitivně, pokud se pro další iterace používá stejná váha, což znamená, že musíme snížit váhy. Stejným způsobem, pokud je gradient záporný, musíme zvýšit váhy. Rovnice aktualizace hmotnosti je

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

kde ${ displaystyle varepsilon}$ představuje chybu střední kvadrát a ${ displaystyle mu}$ je konvergenční koeficient.

Záporné znaménko ukazuje, že klesáme po svahu chyby, ${ displaystyle varepsilon}$ najít hmotnosti filtrů, ${ displaystyle W_ {i}}$, které minimalizují chybu.

Chyba střední kvadratury jako funkce váh filtru je kvadratická funkce, což znamená, že má pouze jedno extrém, které minimalizuje chybu střední kvadrát, což je optimální váha. LMS tedy přistupuje k této optimální váze vzestupně / sestupně dolů křivkou střední kvadratické chyby vs. hmotnosti filtru.

Derivace

Myšlenkou filtrů LMS je použití nejstrmější sestup najít hmotnosti filtrů ${ displaystyle { hat { mathbf {h}}} (n)}$ které minimalizují a nákladová funkce. Začneme definováním nákladové funkce jako

${ displaystyle C (n) = E levý {| e (n) | ^ {2} pravý }}$

kde ${ displaystyle e (n)}$ je chyba v aktuálním vzorku n a ${ displaystyle E { cdot }}$ označuje očekávaná hodnota.

Tato nákladová funkce (${ displaystyle C (n)}$) je střední kvadratická chyba a LMS ji minimalizuje. Tady dostává své jméno LMS. Přihlašování nejstrmější sestup znamená vzít částečné derivace vzhledem k jednotlivým položkám vektoru koeficientu (hmotnosti) filtru

${ displaystyle 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) vpravo }}$

kde ${ displaystyle nabla}$ je spád operátor

${ displaystyle 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)}$

${ displaystyle nabla C (n) = - 2E vlevo { mathbf {x} (n) , e ^ {*} (n) vpravo }}$

Nyní, ${ displaystyle nabla C (n)}$ je vektor, který ukazuje na nejstrmější vzestup nákladové funkce. Abychom našli minimum nákladové funkce, musíme udělat krok opačným směrem než ${ displaystyle nabla C (n)}$. Vyjádřit to matematicky

${ displaystyle { 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 }}$

kde ${ displaystyle { frac { mu} {2}}}$ je velikost kroku (adaptační konstanta). To znamená, že jsme našli algoritmus postupné aktualizace, který minimalizuje nákladovou funkci. Bohužel tento algoritmus není realizovatelný, dokud nebudeme vědět ${ displaystyle E left { mathbf {x} (n) , e ^ {*} (n) right }}$.

Obecně se výše uvedené očekávání nepočítá. Místo toho pro spuštění LMS v online prostředí (aktualizace po obdržení každého nového vzorku) používáme okamžitý odhad tohoto očekávání. Viz. níže.

Zjednodušení

U většiny systémů funkce očekávání ${ displaystyle {E} vlevo { mathbf {x} (n) , e ^ {*} (n) vpravo }}$ musí být přibližné. Toho lze dosáhnout pomocí následujícího nezaujatého odhadce

${ displaystyle { hat {E}} vlevo { mathbf {x} (n) , e ^ {*} (n) vpravo } = { frac {1} {N}} součet _ {i = 0} ^ {N-1} mathbf {x} (ni) , e ^ {*} (ni)}$

kde ${ displaystyle N}$ označuje počet vzorků, které pro tento odhad použijeme. Nejjednodušší případ je ${ displaystyle N = 1}$

${ displaystyle { hat {E}} vlevo { mathbf {x} (n) , e ^ {*} (n) vpravo } = mathbf {x} (n) , e ^ { *} (n)}$

V tomto jednoduchém případě následuje aktualizační algoritmus jako

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

Ve skutečnosti to představuje aktualizační algoritmus pro filtr LMS.

Shrnutí algoritmu LMS

Algoritmus LMS pro a ${ displaystyle p}$Filtr této objednávky lze shrnout jako

Parametry:	${ displaystyle p =}$ pořadí filtrování
	${ displaystyle mu =}$ velikost kroku
Inicializace:	${ displaystyle { hat { mathbf {h}}} (0) = operatorname {nuly} (p)}$
Výpočet:	Pro ${ displaystyle n = 0,1,2, ...}$
	${ displaystyle mathbf {x} (n) = doleva [x (n), x (n-1), tečky, x (n-p + 1) doprava] ^ {T}}$
	${ displaystyle e (n) = d (n) - { hat { mathbf {h}}} ^ {H} (n) mathbf {x} (n)}$
	${ displaystyle { hat { mathbf {h}}} (n + 1) = { hat { mathbf {h}}} (n) + mu , e ^ {*} (n) mathbf { x} (n)}$

Konvergence a stabilita v průměru

Vzhledem k tomu, že algoritmus LMS nepoužívá přesné hodnoty očekávání, váhy by nikdy nedosáhly optimálních vah v absolutním smyslu, ale průměrně je možná konvergence. To znamená, že i když se váhy mohou měnit o malé částky, mění se to o optimálních vahách. Pokud je však rozptyl, s nímž se váhy mění, velký, průměrná konvergence by byla zavádějící. K tomuto problému může dojít, pokud je hodnota velikosti kroku ${ displaystyle mu}$ není zvolen správně.

Li ${ displaystyle mu}$ je zvoleno velké, množství, s nímž se váhy mění, silně závisí na odhadu gradientu, a tak se váhy mohou měnit o velkou hodnotu, takže gradient, který byl v prvním okamžiku záporný, se nyní může stát kladným. A v druhém okamžiku se váha může změnit v opačném směru o velké množství kvůli negativnímu gradientu a bude tak stále oscilovat s velkým rozptylem optimálních vah. Na druhou stranu, pokud ${ displaystyle mu}$ je vybrána jako příliš malá, čas konvergovat na optimální váhy bude příliš velký.

Tudíž horní hranice ${ displaystyle mu}$ je potřeba, která je uvedena jako ${ displaystyle 0 < mu <{ frac {2} { lambda _ { mathrm {max}}}}}$

kde ${ displaystyle lambda _ { max}}$ je největší vlastní hodnota z autokorelace matice ${ displaystyle { mathbf {R}} = E {{ mathbf {x}} (n) { mathbf {x} ^ {H}} (n) }}$. Pokud tato podmínka není splněna, algoritmus se stane nestabilním a ${ displaystyle { hat {h}} (n)}$ rozchází se.

Maximální rychlosti konvergence je dosaženo, když

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

kde ${ displaystyle lambda _ { min}}$ je nejmenší vlastní číslo z ${ displaystyle { mathbf {R}}}$Vzhledem k tomu ${ displaystyle mu}$ je menší nebo rovno tomuto optimu, rychlost konvergence je určena ${ displaystyle lambda _ { min}}$s větší hodnotou přináší rychlejší konvergenci. To znamená, že rychlejší konvergence lze dosáhnout, když ${ displaystyle lambda _ { max}}$ je blízko ${ displaystyle lambda _ { min}}$, tj. maximální dosažitelná rychlost konvergence závisí na šíření vlastního čísla z ${ displaystyle { mathbf {R}}}$.

A bílý šum signál má autokorelační matici ${ displaystyle { mathbf {R}} = sigma ^ {2} { mathbf {I}}}$ kde ${ displaystyle sigma ^ {2}}$ je rozptyl signálu. V tomto případě jsou všechna vlastní čísla stejná a šíření vlastních čísel je minimální ve všech možných maticích. Obecná interpretace tohoto výsledku je tedy taková, že LMS konverguje rychle pro bílé vstupní signály a pomalu pro barevné vstupní signály, jako jsou procesy s nízkými -propustné nebo horní propustné charakteristiky.

Je důležité si uvědomit, že výše uvedená horní hranice ${ displaystyle mu}$ vynucuje stabilitu pouze v průměru, ale koeficienty ${ displaystyle { hat {h}} (n)}$ může stále růst nekonečně velký, tj. divergence koeficientů je stále možná. Praktičtější vazba je

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

kde ${ displaystyle mathrm {tr} [{ mathbf {R}}]}$ označuje stopa z ${ displaystyle { mathbf {R}}}$. Tato vazba zaručuje, že koeficienty ${ displaystyle { hat {h}} (n)}$ se nerozcházejí (v praxi hodnota ${ displaystyle mu}$ by nemělo být zvoleno blízko této horní meze, protože je to poněkud optimistické kvůli aproximacím a předpokladům učiněným při odvození vazby).

Normalizovaný filtr nejmenších středních čtverců (NLMS)

Hlavní nevýhodou „čistého“ algoritmu LMS je, že je citlivý na změnu měřítka svého vstupu ${ displaystyle x (n)}$. Proto je velmi obtížné (ne-li nemožné) zvolit a míra učení ${ displaystyle mu}$ který zaručuje stabilitu algoritmu (Haykin 2002). The Normalizovaný filtr nejmenších středních čtverců (NLMS) je varianta algoritmu LMS, která tento problém řeší normalizací s výkonem vstupu. Algoritmus NLMS lze shrnout jako:

Parametry:	${ displaystyle p =}$ pořadí filtrů
	${ displaystyle mu =}$ velikost kroku
Inicializace:	${ displaystyle { hat { mathbf {h}}} (0) = operatorname {nuly} (p)}$
Výpočet:	Pro ${ displaystyle n = 0,1,2, ...}$
	${ displaystyle mathbf {x} (n) = doleva [x (n), x (n-1), tečky, x (n-p + 1) doprava] ^ {T}}$
	${ displaystyle e (n) = d (n) - { hat { mathbf {h}}} ^ {H} (n) mathbf {x} (n)}$
	${ displaystyle { hat { mathbf {h}}} (n + 1) = { hat { mathbf {h}}} (n) + { frac { mu , e ^ {*} (n ) mathbf {x} (n)} { mathbf {x} ^ {H} (n) mathbf {x} (n)}}}$

Optimální rychlost učení

Lze ukázat, že pokud nedojde k rušení (${ displaystyle v (n) = 0}$), pak je optimální rychlost učení pro algoritmus NLMS

${ displaystyle mu _ {opt} = 1}$

a je nezávislá na vstupu ${ displaystyle x (n)}$ a skutečná (neznámá) impulzní odezva ${ displaystyle mathbf {h} (n)}$. V obecném případě s rušením (${ displaystyle v (n) neq 0}$), optimální rychlost učení je

${ displaystyle mu _ {opt} = { frac {E left [ left | y (n) - { hat {y}} (n) right | ^ {2} right]} {E vlevo [| e (n) | ^ {2} vpravo]}}}$

Výsledky výše předpokládají, že signály ${ displaystyle v (n)}$ a ${ displaystyle x (n)}$ vzájemně nesouvisí, což je v praxi obecně případ.

Důkaz

Nechte vychýlení filtru definovat jako ${ displaystyle Lambda (n) = left | mathbf {h} (n) - { hat { mathbf {h}}} (n) right | ^ {2}}$, můžeme odvodit očekávané vychýlení dalšího vzorku jako:

${ displaystyle 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) vpravo | ^ {2} vpravo]}$

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

Nechat ${ displaystyle mathbf { delta} = { hat { mathbf {h}}} (n) - mathbf {h} (n)}$ a ${ displaystyle r (n) = { hat {y}} (n) -y (n)}$

${ displaystyle 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} right] }$

${ displaystyle E left [ Lambda (n + 1) right] = E left [ left ( mathbf { delta} (n) - { frac { mu , left (v (n) + r (n) vpravo) mathbf {x} (n)} { mathbf {x} ^ {H} (n) mathbf {x} (n)}} vpravo) ^ {H} vlevo ( mathbf { delta} (n) - { frac { mu , left (v (n) + r (n) right) mathbf {x} (n)} { mathbf {x} ^ { H} (n) mathbf {x} (n)}} vpravo) vpravo]}$

Za předpokladu nezávislosti máme:

${ displaystyle 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) }}že jo]}$

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

Optimální rychlost učení se nachází na ${ displaystyle { frac {dE left [ Lambda (n + 1) right]} {d mu}} = 0}$, což vede k:

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

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

Viz také

• Rekurzivní nejmenší čtverce
• Statistické techniky relevantní pro filtr LMS viz Nejmenší čtverce.
• Podobnosti mezi Wiener a LMS
• Adaptivní filtr vícedílné blokové frekvenční domény
• Nulový nulovací ekvalizér
• Adaptivní filtr jádra
• uzavřený filtr
• Wienerův filtr

Reference

• Monson H. Hayes: Statistické zpracování a modelování digitálního signálu, Wiley, 1996, ISBN  0-471-59431-8
• Simon Haykin: Teorie adaptivního filtru, Prentice Hall, 2002, ISBN  0-13-048434-2
• Simon S. Haykin, Bernard Widrow (redaktor): Adaptivní filtry nejmenšího čtverce, Wiley, 2003, ISBN  0-471-21570-8
• Bernard Widrow, Samuel D. Stearns: Adaptivní zpracování signálu, Prentice Hall, 1985, ISBN  0-13-004029-0
• Weifeng Liu, Jose Principe a Simon Haykin: Adaptivní filtrování jádra: komplexní úvod, John Wiley, 2010, ISBN  0-470-44753-2
• Paulo S.R. Diniz: Adaptivní filtrování: Algoritmy a praktická implementace, Kluwer Academic Publishers, 1997, ISBN  0-7923-9912-9

externí odkazy

• Algoritmus LMS v adaptivních anténních polích www.antenna-theory.com
• Ukázka LMS Noise Cancellation www.advsolned.com