まずはCGについての質問を投げておく。 KWBT先生にメール出す前にCGの状況を要約してみよう。
Conjugate Gradient Descent 後ろの方で 、普通の共役勾配方でもモーメンタムがかかっていることを言っている。
18-660: Numerical Methods for Engineering Design and Optimization pre-conditioning（前処理）で共役勾配の性能を維持する方法を紹介。前処理はコレスキー分解に基づいている。
- Conjugate Gradient Method こっちは理論的にもかなり有益そう。もうちょっと見よう。
- 連立1次方程式：共役勾配法 日本語で言ったもの。一般に条件数が悪いと収束特性は悪化する。
- The Conjugate Gradient Method 条件数と収束特性の式が書いてある。 \(\ve{Ax} = \ve{b}\) を解くことを考えたときに、 \(\kappa = \frac{\lambda_{\mathrm{max}}}{\lambda_{\mathrm{min}}}\) を \(\ve{A}\) の条件数とすると、
\begin{equation*} \frac{|| \ve{x} - \ve{x}_{k} ||_{\ve{A}}}{|| \ve{x} - \ve{x}_{0} ||_{\ve{A}}} \leq 2\left( \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1} \right)^{k} \end{equation*}条件数が大きくなると右辺は1に近づき、左辺のノルム比が減りづらくなって収束が遅くなることを示唆している。条件数が1より少し大きいときがベストの挙動か。
なぜ共役勾配が相関付きで悪いのかが分かった。一般に共役勾配法は条件数が悪いと収束特性が悪くなる。そして、次数を上げると条件数は悪化する…ということだと思う。条件数を見てみましょう。
実験の結果、
- 相関付きノイズで自己相関行列の条件数が増大すること
- 同一の相関付きノイズで次数を高めると自己相関行列の条件数が増大すること
が分かった。共役勾配法の限界にぶつかってしまったらしい。
しかし得たものものある。共役勾配法はモーメンタムがかかっているということだ。 AR(p)の逆行列を組み込んでやればええのではないか。
やってみた。がそもそも収束しない。暴れまくる。 \(\ve{Hm} = \delta f\) だから脳死で \(\ve{H} \ve{m}[n] = \delta f[n] \Rightarrow \ve{m}[n] = \ve{H}^{-1} \delta f[n]\) 成り立つだろとか思っていたけど、成り立っていなさそう（実験的に確かめた）。なぜなら \(\ve{m}\) は逐次的に更新しているから。
あと、共役勾配法の自己相関行列の更新は \(\ve{R} \leftarrow \lambda \ve{R} + (1 - \lambda) \ve{x} \ve{x}^{\mathsf{T}}\) では性能が非常に悪く、 \(\ve{R} \leftarrow \lambda \ve{R} + \ve{x} \ve{x}^{\mathsf{T}}\) でないとだめ。これは確かに指数移動平均の極限で見たな。確かに前者が正しい。