\(R^{-1}\) の計算(21)

\begin{equation*} \newcommand\ve[1]{\boldsymbol{#1}} \newcommand\mean[2]{\mathrm{E}_{#1} \left[ #2 \right]} \end{equation*}

昨日あたりから三重対角行列の性質を使ってうまくやれないか...でずっと悩んでいた。

  • （PCAより）共分散行列（今考えてる信号では自己相関行列としてよい、平均0だから）の固有値は各軸の分散になる
  • 自己相関行列の逆はほぼ三重対角行列とみなせる。その行列の要素と固有値には陽な関係がある
  • ある行列の固有値は、その逆行列の固有値の逆数

という3点から攻めればいけるかな、と思ったけど、観測により得られる要素がほとんどなくて、"各軸の分散"も直交変換しないとわからない。という所で詰まっていた。

しばらく悶絶していたら、今考えてるのは直前時刻との相関、つまりAR(1)だから、そいつ共分散の逆行列ならよく知られてるんじゃないと思って探したらすぐに陽な答えが見つかった:

かなり上手い結果が出ている。AR(1)だと仮定してやれば、1つシフトさせたときの相関を求めてしまえば自己相関行列の逆が求まってしまう。

主張としては、1サンプルギャップでの相関が \(0 < \rho < 1\) のとき、 \(N \times N\) の相関行列

\begin{equation*} \ve{R} = \left[ \begin{array}{ccccc} 1 & \rho & \rho^{2} & ... & \rho^{N-1} \\ \rho & 1 & \rho & & \rho^{N-2} \\ \vdots & & \ddots & & \vdots \\ \rho^{N-1} & \rho^{N-2} & ... & & 1 \\ \end{array} \right] \end{equation*}

の逆行列 \(\ve{R}^{-1}\) は

\begin{equation*} \ve{R}^{-1} = \frac{1}{1 - \rho^{2}} \left[ \begin{array}{ccccc} 1 & -\rho & 0 & ... & 0 \\ -\rho & 1 + \rho^{2} & -\rho & \ddots & \vdots \\ 0 & -\rho & \ddots & \ddots & 0 \\ \vdots & \ddots & \ddots & 1 + \rho^{2} & -\rho \\ 0 & ... & 0 & -\rho & 1 \\ \end{array} \right] \end{equation*}

となる。特に、\(\ve{R}\) に信号の分散 \(\sigma^{2}\) を乗じると自己相関行列 \(\ve{K}\) に一致するから

\begin{align*} \ve{K} &= \sigma^{2} \ve{R} \\ \ve{K}^{-1} &= \sigma^{-2} \ve{R}^{-1} \end{align*}

となる。

証明） \(\ve{R}\) はコレスキー（Cholesky）分解によって

\begin{equation*} \ve{R} = \ve{L}\ \mathrm{diag}(1, 1 - \rho^{2}, ..., 1 - \rho^{2})\ \ve{L}^{\mathsf{T}} \end{equation*}

と分解できる。ここで、

\begin{equation*} \ve{L} = \left[ \begin{array}{ccccc} 1 & 0 & 0 & ... & 0 \\ \rho & 1 & 0 & \ddots & \\ \vdots & \rho & 1 & \ddots & 0 \\ \rho^{N-2} & \ddots & \ddots & \ddots & 0 \\ \rho^{N-1} & \rho^{N-2} & ... & \rho & 1 \\ \end{array} \right] \end{equation*}

確認すると、

\begin{align*} & \ve{L}\ \mathrm{diag}(1, 1 - \rho^{2}, ..., 1 - \rho^{2})\ \ve{L}^{\mathsf{T}} \\ &= \left[ \begin{array}{ccccc} 1 & 0 & 0 & ... & 0 \\ \rho & 1 & 0 & \ddots & \\ \vdots & \rho & 1 & \ddots & 0 \\ \rho^{N-2} & \ddots & \ddots & \ddots & 0 \\ \rho^{N-1} & \rho^{N-2} & ... & \rho & 1 \\ \end{array} \right] \left[ \begin{array}{cccc} 1 & & & \\ & 1 - \rho^{2} & & \\ & & \ddots & \\ & & & 1- \rho^{2} \\ \end{array} \right] \left[ \begin{array}{ccccc} 1 & \rho & ... & \rho^{N-2} & \rho^{N-1} \\ 0 & 1 & \rho & \ddots & \rho^{N-2} \\ \vdots & 0 & 1 & \ddots & 0 \\ 0 & \ddots & \ddots & \ddots & \rho \\ 0 & 0 & ... & 0 & 1 \\ \end{array} \right] \\ &= \left[ \begin{array}{ccccc} 1 & 0 & 0 & ... & 0 \\ \rho & 1 - \rho^{2} & 0 & \ddots & \vdots \\ \rho^{2} & \rho(1 - \rho^{2}) & 1 - \rho^{2} & \ddots & 0 \\ \vdots & \vdots & \ddots & \ddots & 0 \\ \rho^{N-1} & \rho^{N-2}(1 - \rho^{2}) & ... & \rho(1 - \rho^{2}) & 1 - \rho^{2} \\ \end{array} \right] \left[ \begin{array}{ccccc} 1 & \rho & ... & \rho^{N-2} & \rho^{N-1} \\ 0 & 1 & \rho & \ddots & \rho^{N-2} \\ \vdots & 0 & 1 & \ddots & 0 \\ 0 & \ddots & \ddots & \ddots & \rho \\ 0 & 0 & ... & 0 & 1 \\ \end{array} \right] \\ &= \left[ \begin{array}{ccccc} 1 & \rho & \rho^{2} & ... & \rho^{N-1} \\ \rho & 1 & \rho & & \rho^{N-2} \\ \vdots & & \ddots & & \vdots \\ \rho^{N-1} & \rho^{N-2} & ... & & 1 \\ \end{array} \right] = \ve{R} \end{align*}

OKであることが分かる。では、 \(\ve{L}^{-1}\) を求めることを考えるが、これは拡張行列に対して行基本変形（ガウスの消去法）を使って求めてみる。 つまり、 \(\left[ \ve{L}\ \ve{I} \right] \rightarrow \left[ \ve{I}\ \ve{L}^{-1} \right]\) として求める。

\begin{align*} \left[ \ve{L}\ \ve{I} \right] &= \left[ \begin{array}{cccccccccc} 1 & 0 & 0 & ... & 0 & 1 & & & & \\ \rho & 1 & 0 & \ddots & & & 1 & & & \\ \vdots & \rho & 1 & \ddots & 0 & & & \ddots & & \\ \rho^{N-2} & \ddots & \ddots & \ddots & 0 & & & & 1 & \\ \rho^{N-1} & \rho^{N-2} & ... & \rho & 1 & & & & & 1 \\ \end{array} \right] \\ & \rightarrow \left[ \begin{array}{cccccccccc} 1 & 0 & 0 & ... & 0 & 1 & & & & \\ 0 & 1 & 0 & \ddots & & -\rho & 1 & & & \\ 0 & \rho & 1 & \ddots & 0 & -\rho^{2} & & \ddots & & \\ \vdots & \ddots & \ddots & \ddots & 0 & \vdots & & & 1 & \\ 0 & \rho^{N-2} & ... & \rho & 1 & -\rho^{N-1} & & & & 1 \\ \end{array} \right] \\ & \rightarrow \left[ \begin{array}{cccccccccc} 1 & 0 & 0 & ... & 0 & 1 & & & & \\ 0 & 1 & 0 & \ddots & & -\rho & 1 & & & \\ 0 & 0 & 1 & \ddots & 0 & 0 & -\rho & \ddots & & \\ \vdots & \ddots & \ddots & \ddots & 0 & \vdots & \vdots & & 1 & \\ 0 & 0 & ... & \rho & 1 & 0 & -\rho^{N-2} & & & 1 \\ \end{array} \right] \\ \rightarrow ... &\rightarrow \left[ \begin{array}{cccccccccc} 1 & 0 & 0 & ... & 0 & 1 & & & & \\ 0 & 1 & 0 & \ddots & & -\rho & 1 & & & \\ 0 & 0 & 1 & \ddots & 0 & 0 & -\rho & \ddots & & \\ \vdots & \ddots & \ddots & \ddots & 0 & \vdots & \ddots & \ddots & 1 & \\ 0 & 0 & ... & 0 & 1 & 0 & ... & 0 & -\rho & 1 \\ \end{array} \right] \end{align*}

よって、

\begin{equation*} \ve{L}^{-1} = \left[ \begin{array}{cccc} 1 & & & \\ -\rho & 1 & & \\ & \ddots & \ddots & \\ & & -\rho & 1 \\ \end{array} \right] \end{equation*}

（下三角行列だからなんかえもい結果でないかな）この結果から、

\begin{align*} \ve{R}^{-1} &= (\ve{L}^{\mathsf{T}})^{-1} \ \mathrm{diag}(1, 1 - \rho^{2}, ..., 1 - \rho^{2})^{-1}\ \ve{L}^{-1} \\ &= (\ve{L}^{-1})^{\mathsf{T}} \ \mathrm{diag}(1, \frac{1}{1 - \rho^{2}}, ..., \frac{1}{1 - \rho^{2}})\ \ve{L}^{-1} \\ &= \frac{1}{1 - \rho^{2}} \left[ \begin{array}{cccc} 1 & -\rho & & \\ & 1 & \ddots & \\ & & \ddots & -\rho \\ & & & 1 \\ \end{array} \right] \left[ \begin{array}{cccc} 1 - \rho^{2} & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1 \\ \end{array} \right] \left[ \begin{array}{cccc} 1 & & & \\ -\rho & 1 & & \\ & \ddots & \ddots & \\ & & -\rho & 1 \\ \end{array} \right] \\ &= \frac{1}{1 - \rho^{2}} \left[ \begin{array}{cccc} 1 - \rho^{2} & -\rho & & \\ & 1 & \ddots & \\ & & \ddots & -\rho \\ & & & 1 \\ \end{array} \right] \left[ \begin{array}{cccc} 1 & & & \\ -\rho & 1 & & \\ & \ddots & \ddots & \\ & & -\rho & 1 \\ \end{array} \right] \\ &= \frac{1}{1 - \rho^{2}} \left[ \begin{array}{ccccc} 1 & -\rho & 0 & ... & 0 \\ -\rho & 1 + \rho^{2} & -\rho & \ddots & \vdots \\ 0 & -\rho & \ddots & \ddots & 0 \\ \vdots & \ddots & \ddots & 1 + \rho^{2} & -\rho \\ 0 & ... & 0 & -\rho & 1 \\ \end{array} \right] \end{align*}

となって結果が確かめられた。

もう一度考えると、i.i.d.雑音のときは有効な情報は分散（の逆数）ということになる。（入力がi.i.d.雑音のとき \(\ve{R}^{-1}\) は対角行列であることは見た） それだけでも収束性能が上がるということは、分散で正規化するだけでも意味がある、というかNLMSとほぼ同じ発想になっている。 このことからもNLMSと同等かそれ以下の性能しか出せないのは頷ける。NGSAでは残差の大きさ入れてないから。

現実の信号は直前サンプルに強い相関を持つのは妥当な仮定。だから良くなるはずというのが自分の印象。 自分、実験いいすか？