Filter der kleinsten mittleren Quadrate - Least mean squares filter

Algorithmen der kleinsten mittleren Quadrate ( LMS ) sind eine Klasse von adaptiven Filtern, die verwendet werden, um ein gewünschtes Filter nachzuahmen, indem die Filterkoeffizienten gefunden werden, die sich auf die Erzeugung des kleinsten mittleren Quadrats des Fehlersignals (Differenz zwischen dem gewünschten und dem tatsächlichen Signal) beziehen. Es ist ein stochastisches Gradientenabstiegsverfahren , bei dem der Filter nur basierend auf dem Fehler zum aktuellen Zeitpunkt angepasst wird. Es wurde 1960 von Professor Bernard Widrow von der Stanford University und seinem ersten Ph.D. Schüler, Ted Hoff .

Problem Formulierung

Beziehung zum Wiener-Filter

Die Realisierung des kausalen Wiener-Filters ähnelt stark der Lösung der Kleinste-Quadrate-Schätzung, außer im Bereich der Signalverarbeitung. Die Kleinste - Quadrate - Lösung, für die Eingangsmatrix und den Ausgangsvektor ist ${\displaystyle\mathbf{X}}$${\displaystyle {\boldsymbol {y}}}$

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

Das FIR-Filter der kleinsten mittleren Quadrate bezieht sich auf das Wiener-Filter, aber das Minimieren des Fehlerkriteriums des ersteren beruht nicht auf Kreuzkorrelationen oder Autokorrelationen. Seine Lösung konvergiert gegen die Wiener Filterlösung. Die meisten linearen adaptiven Filterprobleme können unter Verwendung des obigen Blockdiagramms formuliert werden. Das heißt, ein unbekanntes System soll identifiziert werden, und das adaptive Filter versucht, das Filter so anzupassen , dass es so nahe wie möglich an , wobei nur beobachtbare Signale verwendet werden , und ; aber , und sind nicht direkt beobachtbar. Seine Lösung ist eng mit dem Wiener-Filter verwandt . ${\displaystyle\mathbf{h} (n)}$${\displaystyle {\hat {\mathbf{h}}}(n)}$${\displaystyle\mathbf{h} (n)}$${\displaystyle x(n)}$${\displaystyle d(n)}$${\displaystyle e(n)}$${\displaystyle y(n)}$${\displaystyle v(n)}$${\displaystyle h(n)}$

Definition von Symbolen

${\displaystyle n}$ ist die Nummer des aktuellen Eingangs-Samples

${\displaystyle p}$ ist die Anzahl der Filterabgriffe

${\displaystyle \{\cdot\}^{H}}$( Hermitesche Transponierung oder konjugierte Transponierung )

${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{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)}$geschätzter Filter; interpretieren als Schätzung der Filterkoeffizienten nach n Samples

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

Idee

Die Grundidee hinter dem LMS-Filter besteht darin, sich den optimalen Filtergewichten anzunähern , indem die Filtergewichte so aktualisiert werden, dass sie zum optimalen Filtergewicht konvergieren. Dies basiert auf dem Gradientenabstiegsalgorithmus. Der Algorithmus beginnt mit der Annahme kleiner Gewichte (in den meisten Fällen null) und bei jedem Schritt werden die Gewichte aktualisiert, indem der Gradient des mittleren quadratischen Fehlers ermittelt wird. Das heißt, wenn der MSE-Gradient positiv ist, bedeutet dies, dass der Fehler weiterhin positiv ansteigt, wenn das gleiche Gewicht für weitere Iterationen verwendet wird, was bedeutet, dass wir die Gewichte reduzieren müssen. Auf die gleiche Weise müssen wir die Gewichtungen erhöhen, wenn der Gradient negativ ist. Die Gewichtsaktualisierungsgleichung lautet ${\displaystyle (R^{-1}P)}$

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

wobei stellt den mittleren quadratischen Fehler dar und ist ein Konvergenzkoeffizient. ${\displaystyle\varepsilon}$${\displaystyle\mu}$

Das negative Vorzeichen zeigt, dass wir die Steigung des Fehlers nach unten gehen, um die Filtergewichte zu finden , die den Fehler minimieren. ${\displaystyle\varepsilon}$${\displaystyle W_{i}}$

Der mittlere quadratische Fehler als Funktion der Filtergewichte ist eine quadratische Funktion, was bedeutet, dass er nur ein Extremum hat, das den mittleren quadratischen Fehler minimiert, was das optimale Gewicht ist. Das LMS nähert sich somit diesen optimalen Gewichtungen durch Aufsteigen/Absteigen der Kurve des mittleren quadratischen Fehlers gegenüber der Filtergewichtung.

Ableitung

Die Idee hinter LMS-Filtern besteht darin, den steilsten Abstieg zu verwenden, um Filtergewichte zu finden, die eine Kostenfunktion minimieren . Wir beginnen mit der Definition der Kostenfunktion als ${\displaystyle {\hat {\mathbf{h}}}(n)}$

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

wo ist der Fehler beim aktuellen Sample n und bezeichnet den erwarteten Wert . ${\displaystyle e(n)}$${\displaystyle E\{\cdot\}}$

Diese Kostenfunktion ( ) ist der mittlere quadratische Fehler und wird durch das LMS minimiert. Daher hat das LMS seinen Namen. Das Anwenden des steilsten Abstiegs bedeutet, die partiellen Ableitungen in Bezug auf die einzelnen Einträge des Filterkoeffizienten-(Gewichts-)Vektors zu bilden ${\displaystyle C(n)}$

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

wo der Gradient Operator ${\displaystyle\nabla}$

${\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\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

Nun ist ein Vektor, der auf den steilsten Anstieg der Kostenfunktion zeigt. Um das Minimum der Kostenfunktion zu finden, müssen wir einen Schritt in die entgegengesetzte Richtung von tun . Um das mathematisch auszudrücken ${\displaystyle \nabla C(n)}$${\displaystyle \nabla C(n)}$

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

wo ist die Schrittweite (Anpassungskonstante). Das heißt, wir haben einen sequentiellen Aktualisierungsalgorithmus gefunden, der die Kostenfunktion minimiert. Leider ist dieser Algorithmus nicht realisierbar, bis wir es wissen . ${\displaystyle {\frac {\mu}{2}}}$${\displaystyle E\left\{\mathbf{x} (n)\,e^{*}(n)\right\}}$

Im Allgemeinen wird die obige Erwartung nicht berechnet. Stattdessen verwenden wir zum Ausführen des LMS in einer Online-Umgebung (Aktualisierung nach Erhalt jedes neuen Samples) eine sofortige Schätzung dieser Erwartung. Siehe unten.

Vereinfachungen

Für die meisten Systeme muss die Erwartungsfunktion approximiert werden. Dies kann mit dem folgenden unverzerrten Schätzer erfolgen${\displaystyle {E}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

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

wobei die Anzahl der Stichproben angibt, die wir für diese Schätzung verwenden. Der einfachste Fall ist${\displaystyle N}$${\displaystyle N=1}$

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

Für diesen einfachen Fall folgt der Aktualisierungsalgorithmus als

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

Tatsächlich bildet dies den Aktualisierungsalgorithmus für den LMS-Filter.

Zusammenfassung des LMS-Algorithmus

Der LMS-Algorithmus für Filter a- ter Ordnung kann wie folgt zusammengefasst werden: ${\displaystyle p}$

Parameter:	${\displaystyle p=}$ Filterreihenfolge
	${\displaystyle \mu =}$ Schrittlänge
Initialisierung:	${\displaystyle {\hat {\mathbf {h}}}(0)=\operatorname {Nullen} (p)}$
Berechnung:	Zum ${\displaystyle n=0,1,2,...}$
	${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{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)}$

Konvergenz und Stabilität im Mittel

Da der LMS-Algorithmus nicht die exakten Werte der Erwartungen verwendet, würden die Gewichte im absoluten Sinne nie die optimalen Gewichte erreichen, aber im Mittel ist eine Konvergenz möglich. Das heißt, obwohl sich die Gewichte um kleine Beträge ändern können, ändert es sich um die optimalen Gewichte. Wenn jedoch die Varianz, mit der sich die Gewichte ändern, groß ist, wäre eine Konvergenz des Mittelwerts irreführend. Dieses Problem kann auftreten, wenn der Wert der Schrittweite nicht richtig gewählt ist. ${\displaystyle\mu}$

Wenn groß gewählt wird, hängt der Betrag, mit dem sich die Gewichte ändern, stark von der Gradientenschätzung ab, so dass sich die Gewichte um einen großen Wert ändern können, so dass der Gradient, der im ersten Moment negativ war, nun positiv werden kann. Und im zweiten Moment kann sich das Gewicht aufgrund des negativen Gradienten um einen großen Betrag in die entgegengesetzte Richtung ändern und würde somit mit einer großen Varianz um die optimalen Gewichte weiter schwingen. Wenn andererseits zu klein gewählt wird, wird die Zeit zum Konvergieren zu den optimalen Gewichten zu groß. ${\displaystyle\mu}$${\displaystyle\mu}$

Daher wird eine obere Schranke benötigt, die gegeben ist als ${\displaystyle\mu}$${\displaystyle 0<\mu <{\frac {2}{\lambda _{\mathrm {max} }}}}$

wobei der größte Eigenwert der Autokorrelationsmatrix ist . Ist diese Bedingung nicht erfüllt, wird der Algorithmus instabil und divergiert. ${\displaystyle \lambda_{\max}}$${\displaystyle {\mathbf{R}}=E\{{\mathbf{x}}(n){\mathbf{x}^{H}}(n)\}}$${\displaystyle {\hat{h}}(n)}$

Die maximale Konvergenzgeschwindigkeit wird erreicht, wenn

${\displaystyle \mu ={\frac {2}{\lambda_{\mathrm{max}}+\lambda_{\mathrm{min}}}},}$

wo ist der kleinste Eigenwert von . Unter der Annahme, dass dies kleiner oder gleich diesem Optimum ist, wird die Konvergenzgeschwindigkeit durch bestimmt , wobei ein größerer Wert eine schnellere Konvergenz ergibt. Dies bedeutet, dass eine schnellere Konvergenz erreicht werden kann, wenn nahe bei , dh die maximal erreichbare Konvergenzgeschwindigkeit hängt von der Eigenwertspreizung von ab . ${\displaystyle \lambda_{\min}}$${\displaystyle {\mathbf{R}}}$${\displaystyle\mu}$${\displaystyle \lambda_{\min}}$${\displaystyle \lambda_{\max}}$${\displaystyle \lambda_{\min}}$${\displaystyle {\mathbf{R}}}$

Ein weißes Rauschsignal hat eine Autokorrelationsmatrix, wobei die Varianz des Signals ist. In diesem Fall sind alle Eigenwerte gleich und die Eigenwertspreizung ist das Minimum über alle möglichen Matrizen. Die gängige Interpretation dieses Ergebnisses ist daher, dass das LMS bei weißen Eingangssignalen schnell konvergiert und bei farbigen Eingangssignalen langsam, wie beispielsweise bei Prozessen mit Tiefpass- oder Hochpasscharakteristik. ${\displaystyle {\mathbf{R}}=\sigma^{2}{\mathbf{I}}}$${\displaystyle \sigma ^{2}}$

Es ist wichtig zu beachten, dass die obige obere Schranke nur im Mittel Stabilität erzwingt, aber die Koeffizienten von immer noch unendlich groß werden können, dh eine Divergenz der Koeffizienten ist immer noch möglich. Eine praktischere Grenze ist ${\displaystyle\mu}$${\displaystyle {\hat{h}}(n)}$

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

wobei bezeichnet die Spur von . Diese Grenze garantiert, dass die Koeffizienten von nicht divergieren (in der Praxis sollte der Wert von nicht nahe dieser oberen Grenze gewählt werden, da er aufgrund von Näherungen und Annahmen bei der Ableitung der Grenze etwas optimistisch ist). ${\displaystyle \mathrm {tr} [{\mathbf {R} }]}$${\displaystyle {\mathbf{R}}}$${\displaystyle {\hat{h}}(n)}$${\displaystyle\mu}$

Normalized Least Mean Squares Filter (NLMS)

Der Hauptnachteil des "reinen" LMS-Algorithmus besteht darin, dass er empfindlich auf die Skalierung seiner Eingabe reagiert . Dies macht es sehr schwierig (wenn nicht unmöglich), eine Lernrate zu wählen , die die Stabilität des Algorithmus garantiert (Haykin 2002). Der Normalized Least Mean Squares Filter (NLMS) ist eine Variante des LMS-Algorithmus, der dieses Problem durch Normalisieren mit der Leistung der Eingabe löst. Der NLMS-Algorithmus kann wie folgt zusammengefasst werden: ${\displaystyle x(n)}$ ${\displaystyle\mu}$

Parameter:	${\displaystyle p=}$ Filterreihenfolge
	${\displaystyle \mu =}$ Schrittlänge
Initialisierung:	${\displaystyle {\hat {\mathbf {h}}}(0)=\operatorname {Nullen} (p)}$
Berechnung:	Zum ${\displaystyle n=0,1,2,...}$
	${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{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)}}}$

Optimale Lernrate

Es kann gezeigt werden, dass die optimale Lernrate für den NLMS-Algorithmus ist , wenn keine Interferenz ( ) vorliegt ${\displaystyle v(n)=0}$

${\displaystyle \mu_{opt}=1}$

und ist unabhängig von der Eingabe und der realen (unbekannten) Impulsantwort . Im allgemeinen Fall mit Interferenz ( ) ist die optimale Lernrate ${\displaystyle x(n)}$${\displaystyle\mathbf{h} (n)}$${\displaystyle v(n)\neq 0}$

${\displaystyle \mu_{opt}={\frac {E\left[\left|y(n)-{\hat{y}}(n)\right|^{2}\right]}{E\ links[|e(n)|^{2}\right]}}}$

Die obigen Ergebnisse gehen davon aus, dass die Signale und nicht miteinander korreliert sind, was in der Praxis im Allgemeinen der Fall ist. ${\displaystyle v(n)}$${\displaystyle x(n)}$

Beweis

Die Filterfehlausrichtung sei definiert als , wir können die erwartete Fehlausrichtung für die nächste Probe wie folgt ableiten: ${\displaystyle \Lambda(n)=\left|\mathbf{h}(n)-{\hat{\mathbf{h}}}(n)\right|^{2}}$

${\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)\right| ^{2}\right]}$

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

Lass und${\displaystyle\mathbf{\delta} ={\hat{\mathbf{h}}}(n)-\mathbf{h}(n)}$${\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)\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)}}\rechts)\rechts]}$

Unabhängig davon haben wir:

${\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) }}\Recht]}$

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

Die optimale Lernrate wird bei gefunden , was zu: ${\displaystyle {\frac {dE\left[\Lambda (n+1)\right]}{d\mu}}=0}$

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

Siehe auch

• Rekursive kleinste Quadrate
• Für statistische Techniken, die für LMS-Filter relevant sind, siehe Kleinste Quadrate .
• Ähnlichkeiten zwischen Wiener und LMS
• Adaptiver Filter im Frequenzbereich mit mehreren Verzögerungen
• Nullerzwingender Equalizer
• Adaptiver Kernelfilter
• angepasster Filter
• Wiener-Filter

Verweise

• 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 (Herausgeber): Least-Mean-Square Adaptive Filters, Wiley, 2003, ISBN  0-471-21570-8
• Bernard Widrow, Samuel D. Stearns: Adaptive Signalverarbeitung, Prentice Hall, 1985, ISBN  0-13-004029-0
• Weifeng Liu, Jose Principe und Simon Haykin: Kernel Adaptive Filtering: A Comprehensive Introduction, John Wiley, 2010, ISBN  0-470-44753-2
• Paulo SR Diniz: Adaptive Filtering: Algorithms and Practical Implementation, Kluwer Academic Publishers, 1997, ISBN  0-7923-9912-9

Externe Links

• LMS-Algorithmus in adaptiven Antennenarrays www.antenna-theory.com
• LMS Noise Cancelling- Demo www.advsolned.com