研究会に向けて - 執筆(2)

\begin{equation*} \newcommand\ve[1]{\boldsymbol{#1}} \newcommand\inprod[2]{\langle #1,\ #2 \rangle} \end{equation*}

うーん、SAの原典を探ってるときに

が参照されてて、その中で

が参照されてたけど、全く同じやん…

どうも、Winner解を求める最適化問題のニュートン法を求めると、自己相関行列の逆が自然に出てくるみたい。そして、その適応ステップ版アルゴリズム（LMS Newton Algorithm, 初出はAdaptive Signal Processing(Widrow)）は上記論文と完全に同一。

LMS Newton Algorithmは、Adaptive Signal Processingのp142あたり（Chapter8冒頭）が詳しいが、残差の二乗を目的関数（Adaptive Filter Theory p105 2.38, 2.50に注目）としたときのニュートン法を近似して得られる。導出にあたり勾配を近似（確率降下）することでNewton法が成立している。

適応ステップサイズの設定法には他にもある。

  • 準最適ステップゲインを用いたBlock LMS-Newtonアルゴリズム
    • これはLMS Newton Algorithmに関する話だけど、ここで提案されているやり方をSAに持っていけないか？→ブロック単位で更新しているから話が違う？いや、もうちょっと読み込もう。
      • この論文で可変ステップサイズに関する議論が出てきている。最適係数から垂線を下ろしたところでステップサイズを決めるという方針。それにしたがってNGSAにおいても最適なステップサイズを求めたら今までのNNGSAと同一の結果が出た。
      • 勾配 \(\ve{g}[n] = \mathrm{sgn}(\varepsilon[n])\ve{x}[n]\) に対して \(\inprod{\ve{R}^{-1}\ve{g}[n]}{\ve{h}_{\rm opt} - (\ve{h}[n] + \mu[n] \ve{R}^{-1} \ve{g}[n])}_{\ve{R}} = 0\) を満たす \(\mu[n]\) こそ、勾配のなす方向に対して \(\ve{h}_{\rm opt}\) から垂線を降ろせているから最適になる。直交条件を展開すると、 \(\ve{g}[n]^{\mathsf{T}} \ve{R}^{-1} \ve{R} (\ve{h}_{opt} - \ve{h}[n]) - \mu[n] \ve{g}[n]^{\mathsf{T}} \ve{R}^{-1} \ve{R} \ve{R}^{-1} \ve{g}[n] = 0\) で、 \(\ve{g}[n] = \mathrm{sgn}(\varepsilon[n])\ve{x}[n]\) を突っ込むと \(\mathrm{sgn}(\varepsilon[n]) \ve{x}[n]^{\mathsf{T}} (\ve{h}_{\rm opt} - \ve{h}[n]) - \mu[n] \ve{x}[n]^{\mathsf{T}} \ve{R}^{-1} \ve{x}[n] = \mathrm{sgn}(\varepsilon[n]) \varepsilon[n] + \mathrm{sgn}(\varepsilon[n]) v[n] - \mu[n] \ve{x}[n]^{\mathsf{T}} \ve{R}^{-1} \ve{x}[n] = 0\) より、\(v[n]=0\) ならばいつものステップサイズが出てくる。論文間違ってると思う。。。
      • つまり、NNGSAはその意味でも最適。追記すべきかも。しかし、勾配 \(\ve{g}[n]\) がLMSのときとの差異が気になる。
    • 有益そうなのは、ブロックあたり1回だけ逆行列補題を使うだけでもよいという主張（問題ないことを示している）。つまり自己相関行列の更新を間引く。
  • Analysis of LMS-Newton Adaptive Filtering Algorithms with Variable Convergence Factor Academaから落とした。
    • Newton LMS AlgorithmはRLSと等価。
  • Optimal variable step size for the LMS/Newton algorithm with application to subband adaptive filtering これもAcademiaから

でも、NNGSAまで至らないと上記の一致は指摘できない。また、こっちはFisher情報行列ベースで話を進めているから、射影の足がKLダイバージェンスに一致することを議論できる。

あ、でもNGSAは残差のsgnとってるだけだから、LMS Newton Algorithmのステップサイズを荒く量子化したやつに対応するのか。いや、それでも、ラプラス分布仮定時に最急勾配になってるはずなんや。最適値近傍で頑張って0に近づけるし、しかも遠いときはゆっくり近づいてロングテールな分布を作っているんや。

SAの収束性能解析論文がヒットし始めた