最小二乗フィルタ

最小二乗平均( LMS ) アルゴリズムは、誤差信号 (目的の信号と実際の信号の差) の最小二乗平均を生成することに関連するフィルタ係数を見つけることによって、目的のフィルタを模倣するために使用される適応フィルタの一種です。これは、フィルタが現時点での誤差に基づいてのみ適応されるという点で、確率的勾配降下法です。これは、単層ニューラル ネットワーク ( ADALINE ) の研究に基づいて、スタンフォード大学のBernard Widrow教授と彼の最初の博士課程の学生であるTed Hoffによって 1960 年に発明されました。具体的には、彼らは勾配降下法を使用して ADALINE がパターンを認識できるようにトレーニングし、そのアルゴリズムを「デルタ ルール」と呼びました。次に、彼らはそのルールをフィルタに適用して、 LMS アルゴリズムを作成しました。

この図は、フィルタのさまざまな部分を示しています。 は入力信号であり、これはを使用して一致させたい未知のフィルタによって変換されます。 未知のフィルタからの出力は であり、これはノイズ信号と干渉されて を生成します。 次に、誤差信号が計算され、適応フィルタにフィードバックされて、誤差信号の平均二乗を最小化するようにパラメータが調整されます。 ${\displaystyle x}$${\displaystyle h}$${\displaystyle {\hat {h}}}$${\displaystyle y}$${\displaystyle \nu}$${\displaystyle d=y+\nu }$${\displaystyle e=d-{\hat {y}}=y+\nu -{\hat {y}}}$${\displaystyle e}$

因果ウィーナーフィルタの実現は、信号処理領域を除けば、最小二乗推定の解によく似ています。入力行列と出力ベクトルの最小二乗解 は、 ${\displaystyle \mathbf {X} }$${\displaystyle {\boldsymbol {y}}}$

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

FIR 最小二乗平均フィルタはウィーナー フィルタと関連がありますが、前者の誤差基準を最小化することは相互相関や自己相関に依存しません。その解はウィーナー フィルタの解に収束します。ほとんどの線形適応フィルタリングの問題は、上記のブロック図を使用して定式化できます。つまり、未知のシステムを識別する必要があり、適応フィルタは観測可能な信号、およびのみを使用して、フィルタを にできるだけ近づけるように適応させようとします。ただし、 、および は直接観測できません。その解はウィーナー フィルタと密接に関連しています。 ${\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)}$

${\displaystyle n}$現在の入力サンプルの番号です

${\displaystyle p}$フィルタータップの数

${\displaystyle \{\cdot \}^{H}}$（エルミート転置または共役転置）

${\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)}$推定フィルタ。nサンプル後のフィルタ係数の推定値として解釈する。

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

LMS フィルタの基本的な考え方は、フィルタの重みを更新して最適なフィルタの重みに収束させることで、最適なフィルタの重みに近づくことです。これは、勾配降下アルゴリズムに基づいています。アルゴリズムは、小さな重み (ほとんどの場合はゼロ) を前提として開始し、各ステップで平均二乗誤差の勾配を見つけることで重みを更新します。つまり、MSE 勾配が正の場合、同じ重みを以降の反復に使用すると誤差が正に増加し続けることを意味し、重みを減らす必要があります。同様に、勾配が負の場合、重みを増やす必要があります。重み更新方程式は次のとおりです。 ${\displaystyle (R^{-1}P)}$

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

ここで、は平均二乗誤差を表し、は収束係数です。 ${\displaystyle \epsilon }$${\displaystyle \mu}$

負の符号は、誤差の傾斜を下って、誤差を最小化する フィルタの重みを見つけることを示しています。${\displaystyle \epsilon }$${\displaystyle W_{i}}$

フィルタ重みの関数としての平均二乗誤差は 2 次関数です。つまり、平均二乗誤差を最小化する極値は 1 つだけであり、これが最適な重みです。したがって、LMS は平均二乗誤差対フィルタ重み曲線を上昇/下降することで、この最適な重みに近づきます。

LMSフィルタの考え方は、最急降下法を使ってコスト関数を最小化するフィルタの重みを見つけることです。まずコスト関数を次のように定義します。 ${\displaystyle {\hat {\mathbf {h} }}(n)}$

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

ここで、 は現在のサンプルnにおける誤差であり、 は期待値を表します。 ${\displaystyle e(n)}$${\displaystyle E\{\cdot \}}$

このコスト関数（）は平均二乗誤差であり、LMSによって最小化されます。これがLMSの名前の由来です。最急降下法を適用するということは、フィルタ係数（重み）ベクトルの個々のエントリに関して 偏微分を取ることを意味します。${\displaystyle C(n)}$

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

勾配演算子は どこにありますか${\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\}}$

さて、はコスト関数の最も急な上昇を指すベクトルです。コスト関数の最小値を見つけるには、の反対方向にステップを踏む必要があります。それを数学的に表現すると、 ${\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\}}$

ここで、はステップ サイズ (適応定数) です。つまり、コスト関数を最小化する順次更新アルゴリズムが見つかったことになります。残念ながら、このアルゴリズムは がわかるまで実現できません。 ${\displaystyle {\frac {\mu }{2}}}$${\displaystyle E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

通常、上記の期待値は計算されません。代わりに、LMS をオンライン (新しいサンプルを受信するたびに更新される) 環境で実行するために、その期待値の瞬間的な推定値を使用します。以下を参照してください。

ほとんどのシステムでは、期待関数を近似する必要があります。これは、次の不偏推定量で行うことができます。${\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} (n-i)\,e^{*}(n-i)}$

ここで、は推定に使用したサンプル数を示します。最も単純なケースは${\displaystyle N}$${\displaystyle N=1}$

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

この単純なケースでは更新アルゴリズムは次のようになる。

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

実際、これが LMS フィルターの更新アルゴリズムを構成します。

a次フィルタのLMSアルゴリズムは次のように要約できる。 ${\displaystyle p}$

LMS アルゴリズムは期待値の正確な値を使用しないため、重みは絶対的な意味で最適な重みに到達することはありませんが、平均の収束は可能です。つまり、重みがわずかに変化したとしても、最適な重みを中心に変化します。ただし、重みの変化に伴う分散が大きい場合、平均の収束は誤解を招く可能性があります。この問題は、ステップ サイズの値が正しく選択されていない場合に発生する可能性があります。 ${\displaystyle \mu }$

を大きく選択すると、重みが変化する量は勾配推定値に大きく依存するため、重みが大きく変化して、最初の瞬間に負であった勾配が正になる可能性があります。また、2 番目の瞬間には、負の勾配のために重みが反対方向に大きく変化し、最適な重みを中心に大きな分散で振動し続ける可能性があります。一方、を小さく選択しすぎると、最適な重みに収束するまでの時間が長くなりすぎます。 ${\displaystyle \mu }$${\displaystyle \mu }$

したがって、 の上限が必要となり、それは次のように与えられる 。 ${\displaystyle \mu }$${\displaystyle 0<\mu <{\frac {2}{\lambda _{\mathrm {max} }}}}$

ここで、 は自己相関行列の最大固有値です。この条件が満たされない場合、アルゴリズムは不安定になり、発散します。 ${\displaystyle \lambda _{\max }}$${\displaystyle {\mathbf {R} }=E\{{\mathbf {x} }(n){\mathbf {x} ^{H}}(n)\}}$${\displaystyle {\hat {h}}(n)}$

最大の収束速度は、

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

ここで、は の最小の固有値です。 がこの最適値以下であれば、収束速度は によって決まり、値が大きいほど収束が速くなります。つまり、 がに近いほど収束が速くなります。つまり、達成可能な最大収束速度はの固有値の広がりに依存します。 ${\displaystyle \lambda _{\min }}$${\displaystyle {\mathbf {R} }}$${\displaystyle \mu }$${\displaystyle \lambda _{\min }}$${\displaystyle \lambda _{\max }}$${\displaystyle \lambda _{\min }}$${\displaystyle {\mathbf {R} }}$

ホワイト ノイズ信号には、信号の分散である自己相関行列があります。この場合、すべての固有値は等しく、固有値の広がりはすべての可能な行列で最小になります。したがって、この結果の一般的な解釈は、LMS は白色入力信号に対しては急速に収束し、ローパスまたはハイパス特性を持つプロセスなどの色付き入力信号に対してはゆっくりと収束するというものです。 ${\displaystyle {\mathbf {R} }=\sigma ^{2}{\mathbf {I} }}$${\displaystyle \sigma ^{2}}$

上の上限は平均の安定性のみを強制するものですが、係数は依然として無限に大きくなる可能性があり、つまり係数の発散は依然として可能であることに注意することが重要です。より実用的な上限は ${\displaystyle \mu }$${\displaystyle {\hat {h}}(n)}$

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

ここで、 はのトレースを表します。この境界は、 の係数が発散しないことを保証します (実際には、 の値は、境界の導出時に行われた近似と仮定のためにやや楽観的であるため、この上限に近い値を選択すべきではありません)。 ${\displaystyle \mathrm {tr} [{\mathbf {R} }]}$${\displaystyle {\mathbf {R} }}$${\displaystyle {\hat {h}}(n)}$${\displaystyle \mu }$

「純粋な」LMS アルゴリズムの主な欠点は、入力のスケーリングに敏感であることです。このため、アルゴリズムの安定性を保証する学習率を選択するのは非常に困難 (不可能ではないにしても) です(Haykin 2002)。正規化最小平均二乗フィルタ(NLMS) は、入力の累乗で正規化することでこの問題を解決する LMS アルゴリズムの変形です。NLMS アルゴリズムは次のように要約できます。 ${\displaystyle x(n)}$ ${\displaystyle \mu }$

干渉がない場合（）には、NLMSアルゴリズムの最適学習率は ${\displaystyle v(n)=0}$

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

は入力と実際の（未知の）インパルス応答に依存しない。干渉（）のある一般的なケースでは、最適な学習率は ${\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\left[|e(n)|^{2}\right]}}}$

上記の結果は、信号とが互いに無相関であると仮定しており、これは実際には一般的に当てはまります。 ${\displaystyle v(n)}$${\displaystyle x(n)}$

フィルタのミスアライメントを と定義すると、次のサンプルの予想されるミスアライメントは次のように導出できます。 ${\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]}$

させて、${\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)}}\right)\right]}$

独立性を前提とすると、次のようになります。

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

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

最適な学習率は で見つかり、次のようになります。 ${\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]}}}$

• 再帰最小二乗法
• LMS フィルターに関連する統計手法については、最小二乗法を参照してください。
• WienerとLMSの類似点
• マルチ遅延ブロック周波数領域適応フィルタ
• ゼロフォーシングイコライザー
• カーネル適応フィルタ
• マッチしたフィルタ
• ウィーナーフィルター

• モンソン H. ヘイズ:統計的デジタル信号処理とモデリング、 Wiley、1996 年、ISBN  0-471-59431-8
• サイモン・ヘイキン：適応フィルタ理論、プレンティス・ホール、2002年、ISBN 0-13-048434-2 
• Simon S. Haykin、Bernard Widrow（編）：Least-Mean-Square Adaptive Filters、 Wiley、2003年、ISBN 0-471-21570-8 
• バーナード・ウィドロウ、サミュエル・D・スターンズ：適応信号処理、プレンティス・ホール、1985年、ISBN 0-13-004029-0 
• Weifeng Liu、Jose Principe、Simon Haykin:カーネル適応フィルタリング: 包括的な入門、 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 

• 適応アンテナアレイにおける LMS アルゴリズム www.antenna-theory.com
• LMS ノイズキャンセルデモ www.advsolned.com