デジタル信号処理のための適応フィルタアルゴリズム
再帰的最小二乗法 ( RLS ) は、 入力信号に関連する 重み付き線形最小二乗 コスト関数 を最小化する係数を再帰的に見つける 適応フィルタアルゴリズムです。このアプローチは、 平均二乗誤差の 削減を目的とする 最小平均二乗法 ( LMS ) などの他のアルゴリズムとは対照的です。RLS の導出では、入力信号は 決定論的であると 見なされますが、LMS や同様のアルゴリズムでは、入力信号は 確率的 であると見なされます。ほとんどの競合製品と比較して、RLS は非常に高速な収束を示します。ただし、この利点は、計算の複雑さが増すという代償を伴います。
モチベーション RLSはガウス によって発見されました が、1950年にプラケットが1821年のガウスのオリジナルの研究を再発見するまで使われなかったり無視されたりしていました。一般的に、RLSは適応 フィルタ で解決できるあらゆる問題を解決するために使用できます。たとえば、信号が エコーや ノイズの多いチャネル を介して送信され、次のように受信されるとし
ます。
d （ ん ）
{\displaystyle d(n)}
x （ ん ） =
∑
け = 0
q
b
ん
（ け ） d （ ん − け ） + ヴ （ ん ）
{\displaystyle x(n)=\sum _{k=0}^{q}b_{n}(k)d(nk)+v(n)}
ここで、 は 加法性ノイズ を表します 。RLS フィルタの目的は、 タップ FIR フィルタ を使用して目的の信号を回復することです 。
ヴ （ ん ）
{\displaystyle v(n)}
d （ ん ）
{\displaystyle d(n)}
p + 1
{\displaystyle p+1}
わ
{\displaystyle \mathbf {w} }
d （ ん ） ≈
∑
け = 0
p
わ （ け ） x （ ん − け ） =
わ
T
x
ん
{\displaystyle d(n)\estimate \sum _{k=0}^{p}w(k)x(nk)=\mathbf {w} ^{\mathit {T}}\mathbf {x} _{ n}}
ここで、は 最新のサンプル を含む 列ベクトル です 。回復された所望の信号の推定値は
x
ん
= [ x （ ん ） x （ ん − 1 ） … x （ ん − p ）
]
T
{\displaystyle \mathbf {x} _{n}=[x(n)\quad x(n-1)\quad \ldots \quad x(np)]^{T}}
p + 1
{\displaystyle p+1}
x （ ん ）
{\displaystyle x(n)}
d ^
（ ん ） =
∑
け = 0
p
わ
ん
（ け ） x （ ん − け ） =
わ
ん
T
x
ん
{\displaystyle {\hat {d}}(n)=\sum _{k=0}^{p}w_{n}(k)x(nk)=\mathbf {w} _{n}^{\ mathit {T}}\mathbf {x} _{n}}
目標は、フィルタ のパラメータを推定することで あり、各時点では、 現在の推定値を として参照し 、適応された最小二乗推定値を で参照します 。 は、以下に示すように列ベクトルでもあり、 転置 、 は行ベクトル です 。 行列積 ( と の ドット積 ) は、スカラー です。 が 最小二乗の 意味で大きさが小さい 場合、 推定値は 「良好」 です。
わ
{\displaystyle \mathbf {w} }
ん
{\displaystyle n}
わ
ん
{\displaystyle \mathbf {w} _{n}}
わ
ん + 1
{\displaystyle \mathbf {w} _{n+1}}
わ
ん
{\displaystyle \mathbf {w} _{n}}
わ
ん
T
{\displaystyle \mathbf {w} _{n}^{\mathit {T}}}
わ
ん
T
x
ん
{\displaystyle \mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}}
わ
ん
{\displaystyle \mathbf {w} _{n}}
x
ん
{\displaystyle \mathbf {x} _{n}}
d
^
(
n
)
{\displaystyle {\hat {d}}(n)}
d
^
(
n
)
−
d
(
n
)
{\displaystyle {\hat {d}}(n)-d(n)}
時間が経つにつれて、に関して の 新しい推定値を見つけるために最小二乗アルゴリズムを完全にやり直すことを避けることが望まれます 。
w
n
+
1
{\displaystyle \mathbf {w} _{n+1}}
w
n
{\displaystyle \mathbf {w} _{n}}
RLS アルゴリズムの利点は、行列を反転する必要がないため、計算コストを節約できることです。もう 1 つの利点は、 カルマン フィルター などの結果の背後にある直感が得られることです。
議論 RLS フィルタの背後にある考え方は、 フィルタ係数を適切に選択し、新しいデータが到着するとフィルタを更新することで コスト関数 を最小化することです。エラー信号 と目的の信号は、以下の 負のフィードバック 図で定義されます 。
C
{\displaystyle C}
w
n
{\displaystyle \mathbf {w} _{n}}
e
(
n
)
{\displaystyle e(n)}
d
(
n
)
{\displaystyle d(n)}
誤差は推定値を通じてフィルタ係数に暗黙的に依存します 。
d
^
(
n
)
{\displaystyle {\hat {d}}(n)}
e
(
n
)
=
d
(
n
)
−
d
^
(
n
)
{\displaystyle e(n)=d(n)-{\hat {d}}(n)}
加重最小二乗誤差関数 （最小化したいコスト関数）は、 フィルタ係数にも依存します。
C
{\displaystyle C}
e
(
n
)
{\displaystyle e(n)}
C
(
w
n
)
=
∑
i
=
0
n
λ
n
−
i
e
2
(
i
)
{\displaystyle C(\mathbf {w} _{n})=\sum _{i=0}^{n}\lambda ^{n-i}e^{2}(i)}
ここで、 古いエラー サンプルに指数関数的に小さい重みを与える「忘却係数」です。
0
<
λ
≤
1
{\displaystyle 0<\lambda \leq 1}
コスト関数は、 係数ベクトルのすべての要素の偏微分を取り 、結果をゼロに設定すること
で最小化されます。
k
{\displaystyle k}
w
n
{\displaystyle \mathbf {w} _{n}}
∂
C
(
w
n
)
∂
w
n
(
k
)
=
∑
i
=
0
n
2
λ
n
−
i
e
(
i
)
⋅
∂
e
(
i
)
∂
w
n
(
k
)
=
−
∑
i
=
0
n
2
λ
n
−
i
e
(
i
)
x
(
i
−
k
)
=
0
k
=
0
,
1
,
…
,
p
{\displaystyle {\frac {\partial C(\mathbf {w} _{n})}{\partial w_{n}(k)}}=\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\cdot {\frac {\partial e(i)}{\partial w_{n}(k)}}=-\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\,x(i-k)=0\qquad k=0,1,\ldots ,p}
次に、 エラー信号の定義に
置き換えます。
e
(
n
)
{\displaystyle e(n)}
∑
i
=
0
n
λ
n
−
i
[
d
(
i
)
−
∑
ℓ
=
0
p
w
n
(
ℓ
)
x
(
i
−
ℓ
)
]
x
(
i
−
k
)
=
0
k
=
0
,
1
,
…
,
p
{\displaystyle \sum _{i=0}^{n}\lambda ^{n-i}\left[d(i)-\sum _{\ell =0}^{p}w_{n}(\ell )x(i-\ell )\right]x(i-k)=0\qquad k=0,1,\ldots ,p}
方程式を変形すると、
∑
ℓ
=
0
p
w
n
(
ℓ
)
[
∑
i
=
0
n
λ
n
−
i
x
(
i
−
ℓ
)
x
(
i
−
k
)
]
=
∑
i
=
0
n
λ
n
−
i
d
(
i
)
x
(
i
−
k
)
k
=
0
,
1
,
…
,
p
{\displaystyle \sum _{\ell =0}^{p}w_{n}(\ell )\left[\sum _{i=0}^{n}\lambda ^{n-i}\,x(i-\ell )x(i-k)\right]=\sum _{i=0}^{n}\lambda ^{n-i}d(i)x(i-k)\qquad k=0,1,\ldots ,p}
この形式は行列で表現できる
R
x
(
n
)
w
n
=
r
d
x
(
n
)
{\displaystyle \mathbf {R} _{x}(n)\,\mathbf {w} _{n}=\mathbf {r} _{dx}(n)}
ここで は の 重み付き サンプル共分散 行列であり 、 は と の 間の 相互共分散 の同等の推定値です 。この式に基づいて、コスト関数を最小化する係数を次のように求めます。
R
x
(
n
)
{\displaystyle \mathbf {R} _{x}(n)}
x
(
n
)
{\displaystyle x(n)}
r
d
x
(
n
)
{\displaystyle \mathbf {r} _{dx}(n)}
d
(
n
)
{\displaystyle d(n)}
x
(
n
)
{\displaystyle x(n)}
w
n
=
R
x
−
1
(
n
)
r
d
x
(
n
)
{\displaystyle \mathbf {w} _{n}=\mathbf {R} _{x}^{-1}(n)\,\mathbf {r} _{dx}(n)}
これが議論の主な結果です。
λを選択する が小さいほど 、共分散行列への以前のサンプルの寄与が小さくなります。これにより、フィルタは最近のサンプルに対して より 敏感になり、フィルタ係数の変動が大きくなります。このケースは、 成長ウィンドウRLSアルゴリズム と呼ばれます 。実際には、 は通常0.98から1の間で選択されます。 [1] タイプII最大尤度推定を使用すると 、データセットから最適値を推定できます。 [2]
λ
{\displaystyle \lambda }
λ
=
1
{\displaystyle \lambda =1}
λ
{\displaystyle \lambda }
λ
{\displaystyle \lambda }
再帰アルゴリズム 議論の結果、コスト関数を最小化する係数ベクトルを決定するための単一の方程式が導き出されました。このセクションでは、次の形式の再帰解を導き出したいと思います。
w
n
=
w
n
−
1
+
Δ
w
n
−
1
{\displaystyle \mathbf {w} _{n}=\mathbf {w} _{n-1}+\Delta \mathbf {w} _{n-1}}
ここで、 は時刻における補正係数である 。再帰アルゴリズムの導出は、相互共分散を 次のように表すことから始まる。
Δ
w
n
−
1
{\displaystyle \Delta \mathbf {w} _{n-1}}
n
−
1
{\displaystyle {n-1}}
r
d
x
(
n
)
{\displaystyle \mathbf {r} _{dx}(n)}
r
d
x
(
n
−
1
)
{\displaystyle \mathbf {r} _{dx}(n-1)}
次元データベクトルは
どこに あるか
x
(
i
)
{\displaystyle \mathbf {x} (i)}
p
+
1
{\displaystyle {p+1}}
x
(
i
)
=
[
x
(
i
)
,
x
(
i
−
1
)
,
…
,
x
(
i
−
p
)
]
T
{\displaystyle \mathbf {x} (i)=[x(i),x(i-1),\dots ,x(i-p)]^{T}}
同様に、を次の
ように 表す。
R
x
(
n
)
{\displaystyle \mathbf {R} _{x}(n)}
R
x
(
n
−
1
)
{\displaystyle \mathbf {R} _{x}(n-1)}
係数ベクトルを生成するために、決定論的自己共分散行列の逆行列が重要になります。このタスクには、 ウッドベリー行列恒等式 が便利です。
ウッドベリー行列の恒等式は次のようになる。
標準的な文献に沿うように、我々は定義する
ここで ゲインベクトル は
g
(
n
)
{\displaystyle g(n)}
先に進む前に、 別の形で
g
(
n
)
{\displaystyle \mathbf {g} (n)}
左辺の2番目の項を引くと、
望ましい形式
の再帰定義は次のようになる。
P
(
n
)
{\displaystyle \mathbf {P} (n)}
g
(
n
)
=
P
(
n
)
x
(
n
)
{\displaystyle \mathbf {g} (n)=\mathbf {P} (n)\mathbf {x} (n)}
これで再帰を完了する準備ができました。
2番目のステップは の再帰的定義から得られる 。次に の再帰的定義を の 別の形式と組み合わせる と、
r
d
x
(
n
)
{\displaystyle \mathbf {r} _{dx}(n)}
P
(
n
)
{\displaystyle \mathbf {P} (n)}
g
(
n
)
{\displaystyle \mathbf {g} (n)}
更新方程式に到達する
と
w
n
−
1
=
P
(
n
−
1
)
r
d
x
(
n
−
1
)
{\displaystyle \mathbf {w} _{n-1}=\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)}
ここで、 事前 誤差
です 。これを 事後 誤差、つまりフィルタが更新された
後に 計算される誤差と比較してください。
α
(
n
)
=
d
(
n
)
−
x
T
(
n
)
w
n
−
1
{\displaystyle \alpha (n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n-1}}
e
(
n
)
=
d
(
n
)
−
x
T
(
n
)
w
n
{\displaystyle e(n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n}}
つまり、補正係数が見つかったということです
Δ
w
n
−
1
=
g
(
n
)
α
(
n
)
{\displaystyle \Delta \mathbf {w} _{n-1}=\mathbf {g} (n)\alpha (n)}
この直感的に納得のいく結果は、補正係数が誤差とゲイン ベクトルの両方に正比例し、重み係数を通じてどの程度の感度が望ましいかを制御することを示しています 。
λ
{\displaystyle \lambda }
RLSアルゴリズムの概要 p 次RLSフィルタのRLSアルゴリズムは 次のように要約できる。
の再帰は 代数リカッチ方程式 に従うため、 カルマンフィルタ と類似している 。 [3]
P
{\displaystyle P}
格子再帰最小二乗フィルタ (LRLS) 格子 再帰最小二乗 適応フィルタは、 より少ない算術演算（ N 次）を必要とする点を除いて、標準 RLS と関連している。 [4] 従来の LMS アルゴリズムに比べて、収束速度が速い、モジュール構造、入力相関行列の固有値拡散の変化に対する鈍感さなどの利点がある。ここで説明する LRLS アルゴリズムは 事後 誤差に基づいており、正規化された形式を含む。導出は標準 RLS アルゴリズムに似ており、の定義に基づいている 。前方予測の場合、 入力信号は 最新のサンプルである。後方予測の場合は であり 、ここで i は予測する過去のサンプルのインデックスであり、入力信号 は最新のサンプルである。 [5]
d
(
k
)
{\displaystyle d(k)\,\!}
d
(
k
)
=
x
(
k
)
{\displaystyle d(k)=x(k)\,\!}
x
(
k
−
1
)
{\displaystyle x(k-1)\,\!}
d
(
k
)
=
x
(
k
−
i
−
1
)
{\displaystyle d(k)=x(k-i-1)\,\!}
x
(
k
)
{\displaystyle x(k)\,\!}
パラメータの概要
κ
f
(
k
,
i
)
{\displaystyle \kappa _{f}(k,i)\,\!}
前方反射係数
κ
b
(
k
,
i
)
{\displaystyle \kappa _{b}(k,i)\,\!}
後方反射係数
e
f
(
k
,
i
)
{\displaystyle e_{f}(k,i)\,\!}
瞬間的な 事後 予測誤差を表す
e
b
(
k
,
i
)
{\displaystyle e_{b}(k,i)\,\!}
瞬間的な 事後 予測誤差を表す
ξ
b
min
d
(
k
,
i
)
{\displaystyle \xi _{b_{\min }}^{d}(k,i)\,\!}
最小二乗後方予測誤差は最小である
ξ
f
min
d
(
k
,
i
)
{\displaystyle \xi _{f_{\min }}^{d}(k,i)\,\!}
最小二乗法による前方予測誤差の最小値
γ
(
k
,
i
)
{\displaystyle \gamma (k,i)\,\!}
事前誤差 と 事後 誤差 の変換係数である
v
i
(
k
)
{\displaystyle v_{i}(k)\,\!}
フィードフォワード乗算係数です。
ε
{\displaystyle \varepsilon \,\!}
0.01の小さな正の定数である。
LRLSアルゴリズムの概要 LRLSフィルタのアルゴリズムは次のように要約できる。
正規化格子再帰最小二乗フィルタ (NLRLS) LRLS の正規化された形式には、再帰と変数が少なくなります。これは、アルゴリズムの内部変数に正規化を適用することで計算でき、その大きさは 1 に制限されます。これは、計算負荷が大きくなる除算と平方根演算の数が多いため、通常、リアルタイム アプリケーションでは使用されません。
NLRLSアルゴリズムの概要 NLRLSフィルタのアルゴリズムは次のように要約できる。
参照
参考文献 Hayes, Monson H. (1996)。「9.4: 再帰的最小二乗法」。 統計的デジタル信号処理およびモデリング 。Wiley。p. 541。ISBN 0-471-59431-8 。 サイモン・ヘイキン 『適応フィルタ理論』 、プレンティス・ホール、2002年、 ISBN 0-13-048434-2 MHA Davis、RB Vinter、 「確率的モデリングと制御」 、Springer、1985年、 ISBN 0-412-16200-8 Weifeng Liu、Jose Principe、Simon Haykin、 『カーネル適応フィルタリング：包括的入門』 、John Wiley、2010年、 ISBN 0-470-44753-2 RLPlackett, 最小二乗法におけるいくつかの定理 , Biometrika, 1950, 37, 149–157, ISSN 0006-3444 CFGauss、 理論の組み合わせは観測誤差の最小値 、1821 年、ヴェルケ、4. ゲッティンゲ
注記
^ Emannual C. Ifeacor、Barrie W. Jervis。デジタル信号処理：実践的アプローチ、第2版。インディアナポリス：Pearson Education Limited、2002年、p. 718 ^ Steven Van Vaerenbergh、Ignacio Santamaría、Miguel Lázaro-Gredilla「カーネル再帰最小二乗法における忘却係数の推定」、2012 IEEE International Workshop on Machine Learning for Signal Processing、2012、2016 年 6 月 23 日アクセス。 ^ Welch, Greg および Bishop, Gary「カルマン フィルタ入門」、ノースカロライナ大学チャペルヒル校コンピュータ サイエンス学部、1997 年 9 月 17 日、2011 年 7 月 19 日にアクセス。 ^ Diniz, Paulo SR、「適応フィルタリング：アルゴリズムと実用的な実装」、Springer Nature Switzerland AG 2020、第 7 章：適応型ラティスベース RLS アルゴリズム。https://doi.org/10.1007/978-3-030-29057-3_7 ^ Albu、Kadlec、Softley、Matousek、Hermanek、Coleman、Fagan「Virtex での (正規化された) RLS ラティスの実装」、デジタル信号処理、2001 年、2011 年 12 月 24 日にアクセス。
![{\displaystyle \mathbf {x} _{n}=[x(n)\quad x(n-1)\quad \ldots \quad x(np)]^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09eb921b307dabe5f3f396085912215d09c02114)
![{\displaystyle \sum _{i=0}^{n}\lambda ^{ni}\left[d(i)-\sum _{\ell =0}^{p}w_{n}(\ell )x(i-\ell )\right]x(ik)=0\qquad k=0,1,\ldots ,p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19ddcbc3bdad707cdb76a5d5371bc1bee9872174)
![{\displaystyle \sum _{\ell =0}^{p}w_{n}(\ell )\left[\sum _{i=0}^{n}\lambda ^{ni}\,x(i-\ell )x(ik)\right]=\sum _{i=0}^{n}\lambda ^{ni}d(i)x(ik)\qquad k=0,1,\ldots ,p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5289d4da73b7a149fdf9a53cbd8c80a11c0dfe6)
![{\displaystyle \mathbf {x} (i)=[x(i),x(i-1),\dots ,x(ip)]^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dab2ea44a54d82de74ac9f6d26e3f5f6c2a44d8a)
