Filtr najmniejszych średnich kwadratów

najmniejszych średnich kwadratów ( LMS ) to klasa filtrów adaptacyjnych używanych do naśladowania pożądanego filtra poprzez znajdowanie współczynników filtra, które odnoszą się do wytwarzania najmniejszego średniego kwadratu sygnału błędu (różnica między pożądanym a rzeczywistym sygnałem). Jest to stochastycznego spadku gradientu , w której filtr jest dostosowywany tylko na podstawie błędu w bieżącym czasie. Został wynaleziony w 1960 roku przez profesora Uniwersytetu Stanforda Bernarda Widrowa i jego pierwszy doktorat. uczeń Teda Hoffa .

Sformułowanie problemu

Związek z filtrem Wienera

Realizacja przyczynowego filtra Wienera wygląda bardzo podobnie do rozwiązania estymacji metodą najmniejszych kwadratów, z wyjątkiem dziedziny przetwarzania sygnału. Rozwiązanie najmniejszych kwadratów dla macierzy wejściowej i wektora wyjściowego $}}$${\ displaystyle \ mathbf {X}$

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

Filtr FIR najmniejszych średnich kwadratów jest powiązany z filtrem Wienera, ale minimalizacja kryterium błędu pierwszego nie opiera się na korelacjach krzyżowych ani autokorelacjach. Jego rozwiązanie jest zbieżne z rozwiązaniem filtru Wienera. Większość problemów z liniowym filtrowaniem adaptacyjnym można sformułować za pomocą powyższego schematu blokowego. Oznacza to, że nieznany system $h} }}(n)}$ zostać zidentyfikowany, a filtr adaptacyjny próbuje dostosować filtr $Displaystyle$${\ mathbf$$Displaystyle x (n)}$ jak najbardziej zbliżony do , $( n$ tylko obserwowalnych sygnałów $re (n)}$$\$ Displaystyle i ${\ Displaystyle e (n)}$ ; ale ${\ Displaystyle y (n)}$ , ${\ Displaystyle v (n)}$ i ${\ displaystyle h (n)}$ nie są bezpośrednio obserwowalne. Jego rozwiązanie jest ściśle związane z filtrem Wienera .

Definicja symboli

${\ displaystyle n}$ to numer bieżącej próbki wejściowej

${\ displaystyle p}$ to liczba stuknięć filtra

${\ Displaystyle \ {\ cdot \} ^ {H}}$ ( Transpozycja hermitowska lub transpozycja sprzężona )

${\ Displaystyle \ mathbf {x} (n) = \ lewo [x (n), x (n-1), \ kropki, x (np-1) \ prawo] ^ {T}}$

${\ Displaystyle \ mathbf {h} (n) = \ lewo [h_ {0} (n), h_ {1} (n), \ kropki, h_ {p-1} (n) \ prawej] ^ {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)}$ szacowany filtr; interpretować jako oszacowanie współczynników filtra po n próbkach

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

Pomysł

Podstawową ideą filtra LMS jest zbliżenie się do optymalnych wag filtrów ${\ Displaystyle (R ^ {- 1} P)}$ , aktualizując wagi filtrów w taki sposób, aby uzyskać zbieżność z optymalną wagą filtrów. Jest to oparte na algorytmie opadania gradientu. Algorytm rozpoczyna się od przyjęcia małych wag (w większości przypadków zerowych) i na każdym kroku, poprzez znalezienie gradientu błędu średniokwadratowego, wagi są aktualizowane. Oznacza to, że jeśli gradient MSE jest dodatni, oznacza to, że błąd będzie wzrastał dodatnio, jeśli ta sama waga zostanie użyta w dalszych iteracjach, co oznacza, że ​​musimy zmniejszyć wagi. W ten sam sposób, jeśli gradient jest ujemny, musimy zwiększyć wagi. Równanie aktualizacji wagi jest

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

gdzie reprezentuje $średniokwadratowy$ i jest $zbieżności$ .

Znak ujemny pokazuje, że schodzimy w dół zbocza błędu, $aby$$znaleźć$ wagi filtrów , które

Błąd średniokwadratowy jako funkcja wag filtrów jest funkcją kwadratową, co oznacza, że ​​ma tylko jedno ekstremum, które minimalizuje błąd średniokwadratowy, czyli wagę optymalną. W ten sposób LMS zbliża się do tych optymalnych wag, wznosząc się/spadając w dół krzywej średniego błędu kwadratowego w stosunku do masy filtra.

Pochodzenie

Ideą filtrów LMS jest użycie $najbardziej$ spadku w celu znalezienia wag filtrów , które Zaczynamy od zdefiniowania funkcji kosztu jako

${\ Displaystyle C (n) = E \ lewo \ {| e (n) | ^ {2} \ prawo \}}$

gdzie $n)}$$i$ Displaystyle e jest błędem w bieżącej próbce n oznacza wartość

Ta funkcja kosztu ( $średniokwadratowym i$ przez LMS Od tego LMS bierze swoją nazwę. Zastosowanie najbardziej stromego spadku oznacza pobranie pochodnych cząstkowych względem poszczególnych wpisów wektora współczynników (wag) filtra

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

gdzie $_$ operatorem gradientu _

${\ Displaystyle \ nabla _ {{\ kapelusz {\ 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 \ lewo \ {\ mathbf {x} (n) \ e ^ {*} (n )\Prawidłowy\}}$

Teraz jest wektorem, który wskazuje na najbardziej strome wzniesienie funkcji kosztu. do $(n)}$ Aby znaleźć minimum funkcji kosztu, musimy zrobić krok w przeciwnym kierunku niż ${\ Displaystyle \ nabla C (n)}$ . Aby wyrazić to w kategoriach matematycznych

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

gdzie $jest$ wielkością kroku (stała adaptacji Oznacza to, że znaleźliśmy algorytm aktualizacji sekwencyjnej, który minimalizuje funkcję kosztu. Niestety, ten algorytm nie jest możliwy do zrealizowania, dopóki nie wiemy, że ${\ Displaystyle E \ lewo \ {\ mathbf {x} (n) \, e ^ {*} (n) \ prawo \}}$ .

Ogólnie rzecz biorąc, powyższe oczekiwanie nie jest obliczane. Zamiast tego, aby uruchomić LMS w środowisku online (aktualizacja po otrzymaniu każdej nowej próbki), używamy natychmiastowego oszacowania tego oczekiwania. Zobacz poniżej.

uproszczenia

W przypadku większości systemów funkcja oczekiwań ${\ Displaystyle {E} \ lewo \ {\ mathbf {x} (n) \, e ^ {*} (n) \ prawo \} }$ musi być przybliżone. Można to zrobić za pomocą następującego nieobciążonego estymatora

${\ Displaystyle {\ kapelusz {E}} \ lewo \ {\ mathbf {x} (n)\,e^{*}(n)\right\}={\frac {1}{N}}\sum _{i=0}^{N-1}\mathbf {x } (ni)\,e^{*}(ni)}$

gdzie $wskazuje$ liczbę próbek, których używamy do tego oszacowania Najprostszym przypadkiem jest ${\ displaystyle N = 1}$

${\ Displaystyle {\ kapelusz {E}} \ lewo \ {\ mathbf {x} (n) \, e ^ { *}(n)\right\}=\mathbf {x} (n)\,e^{*}(n)}$

W tym prostym przypadku algorytm aktualizacji wygląda następująco

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

Rzeczywiście, stanowi to algorytm aktualizacji dla filtra LMS.

Podsumowanie algorytmu LMS

Algorytm LMS dla filtra tego rzędu można podsumować jako ${\ displaystyle p}$

Parametry:	${\ displaystyle p =}$ kolejność filtrów
	${\ Displaystyle \ mu =}$ rozmiar kroku
Inicjalizacja:	${\ Displaystyle {\ kapelusz {\ mathbf {h}}} (0) = \ operatorname {zera} (p)}$
Obliczenie:	Dla ${\ displaystyle n = 0,1,2,...}$
	${\ Displaystyle \ mathbf {x} (n) = \ lewo [x (n), x(n-1),\kropki ,x(n-p+1)\right]^{T}}$
	${\ Displaystyle e (n) = re (n) - {\ kapelusz {\ mathbf {h}}} ^ {H} (n) \ mathbf {x} (n)}$
	${\ Displaystyle {\ kapelusz {\ mathbf {h}}} (n + 1) = {\ kapelusz {\ mathbf {h}}} (n )+\mu \,e^{*}(n)\mathbf {x} (n)}$

Zbieżność i stabilność w średniej

Ponieważ algorytm LMS nie wykorzystuje dokładnych wartości oczekiwań, wagi nigdy nie osiągnęłyby optymalnych wag w sensie bezwzględnym, ale możliwa jest zbieżność w średniej. Oznacza to, że nawet jeśli wagi mogą się zmieniać o niewielkie wartości, zmienia się o optymalne wagi. Jeśli jednak wariancja, z jaką zmieniają się wagi, jest duża, zbieżność średniej byłaby myląca. $wystąpić$ , jeśli wartość kroku zostanie wybrana prawidłowo.

Jeśli zostanie wybrane $duże$ , wielkość, o jaką zmieniają się wagi, zależy w dużej mierze od oszacowania gradientu, więc wagi mogą się zmienić o dużą wartość, tak że gradient, który był ujemny w pierwszej chwili, może stać się pozytywnym. A w drugiej chwili waga może zmienić się w przeciwnym kierunku o dużą wartość z powodu ujemnego gradientu, a zatem oscylowałaby z dużą wariancją w stosunku do optymalnych wag. Z drugiej strony, jeśli zostanie wybrane jako zbyt małe, czas dojścia do optymalnych wag będzie zbyt $długi$

Zatem potrzebna jest górna granica na ${\ displaystyle \ mu}$ , która jest podana jako ${\ Displaystyle 0 <\ mu <{\ Frac {2} {\ lambda _ {\ operatorname {max } }}}}$

gdzie ${\ Displaystyle \ lambda _ {\ max}}$ jest największą wartością własną macierzy autokorelacji ${\ Displaystyle {\ mathbf {R}} = E \ { {\mathbf {x}}(n){\mathbf {x} ^{H}}(n)\}}$ . Jeśli $warunek nie$ spełniony, algorytm staje się .

Maksymalna prędkość zbieżności jest osiągana, gdy

${\ Displaystyle \ mu = {\ Frac {2} {\ lambda _ {\ operatorname {max}} + \ lambda _ {\ operatorname {min}}}}, }$

gdzie jest najmniejszą wartością własną ${\ Displaystyle {\ mathbf {R}$$}}$ } Biorąc pod uwagę $,$ że jest $czym$ lub równe temu optimum, prędkość zbieżności jest określana przez większa wartość daje szybszą zbieżność $, że$ zbieżność można osiągnąć, gdy blisko ${\ Displaystyle \ lambda _ {\ min}}$ , czyli maksymalna osiągalna prędkość zbieżności zależy od rozrzutu wartości własnych R $\ Displaystyle {\ mathbf {R}}}$ .

Sygnał białego szumu ma macierz autokorelacji $ja {\ Displaystyle {\ mathbf {R}} = \ sigma ^ {2} {\ mathbf {I$$}$ jest wariancją sygnału. W tym przypadku wszystkie wartości własne są równe, a rozrzut wartości własnych jest minimalny we wszystkich możliwych macierzach. Powszechna interpretacja tego wyniku jest zatem taka, że ​​LMS zbiega się szybko dla białych sygnałów wejściowych i powoli dla kolorowych sygnałów wejściowych, takich jak procesy o charakterystyce dolnoprzepustowej lub górnoprzepustowej.

Należy zauważyć, że powyższa górna granica $średniej$$jedynie$ ale współczynniki nadal nieskończenie duża, tj. rozbieżność współczynników jest nadal możliwa. Bardziej praktycznym ograniczeniem jest

${\ Displaystyle 0 <\ mu <{\ Frac {2} {\ operatorname {tr} \ lewo [{\ mathbf {R}} \ prawej]}}}$

gdzie $\ Displaystyle$ ślad R { $}}$ . Ta granica gwarantuje, że współczynniki nie rozchodzą się (w praktyce wartość $powinna być$ blisko tego $displaystyle \ mu$ górna granica, ponieważ jest nieco optymistyczna ze względu na przybliżenia i założenia przyjęte przy wyprowadzaniu granicy).

Znormalizowany filtr najmniejszych średnich kwadratów (NLMS)

Główną wadą „czystego” algorytmu LMS jest to, że jest on wrażliwy na skalowanie danych wejściowych ${\ displaystyle x (n)}$ . To bardzo utrudnia (jeśli nie uniemożliwia) wybranie $,$ uczenia się która gwarantuje stabilność algorytmu (Haykin 2002). Znormalizowany filtr najmniejszych średnich kwadratów (NLMS) to wariant algorytmu LMS, który rozwiązuje ten problem poprzez normalizację z mocą wejścia. Algorytm NLMS można podsumować jako:

Parametry:	${\ displaystyle p =}$ kolejność filtrów
	${\ Displaystyle \ mu =}$ rozmiar kroku
Inicjalizacja:	${\ Displaystyle {\ kapelusz {\ mathbf {h}}} (0) = \ operatorname {zera} (p)}$
Obliczenie:	Dla ${\ displaystyle n = 0,1,2,...}$
	${\ Displaystyle \ mathbf {x} (n) = \ lewo [x (n), x(n-1),\kropki ,x(n-p+1)\right]^{T}}$
	${\ Displaystyle e (n) = re (n) - {\ kapelusz {\ mathbf {h}}} ^ {H} (n) \ mathbf {x} (n)}$
	${\ Displaystyle {\ kapelusz {\ mathbf {h}}} (n + 1) = {\ kapelusz {\ mathbf {h}}} (n) + {\ Frac {\ mu \, e ^ {*} (n )\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}}$

Optymalna szybkość uczenia się

Można pokazać, że jeśli nie ma interferencji ( ) , to optymalna szybkość uczenia się algorytmu NLMS wynosi v $\ displaystyle v (n) = 0}$

${\ Displaystyle \ mu _ {opt} = 1}$

$i$$jest$ od rzeczywistej odpowiedzi W ogólnym przypadku z interferencją ( ) optymalnym współczynnikiem uczenia się jest ${\ Displaystyle v (n) \ neq 0}$

${\ Displaystyle \ mu _ {opt} = {\ Frac {E \ lewo [\ lewo | y (n) - {\ kapelusz {y}} (n) \ prawo | ^ {2} \ prawo]} { E\lewo[|e(n)|^{2}\prawo]}}}$

$zakładają$ że sygnały i są $miejsce$ sobą, co zwykle

Dowód

Niech niewspółosiowość filtra będzie zdefiniowana jako $| ^ {2}}$ prawo niewspółosiowość dla następnej próbki jako:

${\ Displaystyle E \ lewo [\ Lambda (n + 1) \ prawo] = E \ lewo [\ lewo | {\ kapelusz {\ mathbf {h}}} (n) + {\ Frac {\ mu \, e ^ {*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right| ^{2}\right]}$

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

Niech $_$ _ ${\ Displaystyle r (n) = {\ kapelusz {y}} (n) -y (n)}$

${\ Displaystyle E \ lewo [\ Lambda (n + 1) \ prawo] = E \ lewo [\ lewo | \ mathbf {\ delta} (n) - {\ Frac {\ mu \, \ lewo (v (n) +r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right|^{2}\right] }$

${\ Displaystyle E \ lewo [\ Lambda (n + 1) \ prawo] = E \ lewo [\ lewo (\ mathbf {\ delta} (n) - {\ Frac {\ mu \, \ lewo (v (n) +r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left( \mathbf {\delta} (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{ H}(n)\mathbf {x} (n)}}\prawo)\prawo]}$

Zakładając niezależność mamy:

${\ Displaystyle E \ lewo [\ Lambda (n + 1) \ prawo] = \ Lambda (n) + E \ lewo [\ lewo ({\ Frac {\ mu \, \ lewo (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]}$

${\ Displaystyle E \ lewo [\ Lambda (n + 1) \ prawo] = \ Lambda (n) + {\ Frac {\ mu ^ {2} E \ lewo [| 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)}}}$

Optymalny wskaźnik uczenia się znajduje się przy ${\ Displaystyle {\ Frac {dE \ lewo [\ Lambda (n + 1) \ prawo]} {d \ mu}} = 0 }$ , co prowadzi do:

${\ Displaystyle 2 \ mu E \ lewo [| e (n) | ^ {2} \ prawo] -2E \ lewo [| r (n) | ^ {2} \ prawo] = 0}$

${\ Displaystyle \ mu = {\ Frac {E \ lewo [| r (n) | ^ {2} \ prawo]} {E \ lewo [| e (n) | ^ {2} \ prawo]}}}$

Zobacz też

• Rekurencyjne metody najmniejszych kwadratów
• Aby zapoznać się z technikami statystycznymi związanymi z filtrem LMS, patrz Metoda najmniejszych kwadratów .
• Podobieństwa między Wienerem a LMS
• Filtr adaptacyjny w domenie częstotliwości bloków z wieloma opóźnieniami
• Korektor wymuszający zero
• Filtr adaptacyjny jądra
• Dopasowany filtr
• filtr Wienera

•   Monson H. Hayes: statystyczne przetwarzanie i modelowanie sygnałów cyfrowych, Wiley, 1996, ISBN 0-471-59431-8
•   Simon Haykin: adaptacyjna teoria filtrów , Prentice Hall, 2002, ISBN 0-13-048434-2
•   Simon S. Haykin, Bernard Widrow (redaktor): Adaptacyjne filtry najmniejszej średniej kwadratowej , Wiley, 2003, ISBN 0-471-21570-8
•   Bernard Widrow, Samuel D. Stearns: Adaptacyjne przetwarzanie sygnału , Prentice Hall, 1985, ISBN 0-13-004029-0
•   Weifeng Liu, Jose Principe i Simon Haykin: Adaptacyjne filtrowanie jądra: kompleksowe wprowadzenie , John Wiley, 2010, ISBN 0-470-44753-2
•   Paulo SR Diniz: Filtrowanie adaptacyjne: algorytmy i praktyczne wdrożenie , Kluwer Academic Publishers, 1997, ISBN 0-7923-9912-9

Linki zewnętrzne

• Algorytm LMS w adaptacyjnych macierzach antenowych www.antenna-theory.com
• Demo redukcji szumów LMS www.advsolned.com