\begin{equation*}
\newcommand\innerp[2]{\langle #1, #2 \rangle}
\newcommand\ve[1]{\boldsymbol{#1}}
\newcommand\parfrac[2]{\frac{\partial #1}{\partial #2}}
\newcommand\mean[2]{\mathrm{E}_{#1} \left[ #2 \right]}
\newcommand\KL[2]{\mathrm{KL} \left[ #1 \ \middle| \middle| \ #2 \right]}
\end{equation*}
\(\ve{R}\) はToeplitz（テプリッツ行列）だから、それをFFTベースで高速計算する手法がある（テプリッツ法というらしい）
『ガウス過程と機械学習』によると、テプリッツ行列を巡回行列に展開して、それに対してFFTを実行して \(\mathcal{O}(nlogn)\) で処理を進めるというもの。ただし本には明らかな誤りがある。巡回行列の1行目は \([ K_{1,1} K_{1,2} ... K_{1,M-1} K_{1,M} K_{1,M-1} K_{1,M-1} ... K_{1,2} ]\) のはずだ。そうじゃないと巡回して行列を作ったときにおかしなことになる。
他にも論文がある。下はFFTベースの手法のようだ。
思ったのが、一般の自然勾配法において超巨大なFisher情報行列に対してこれは使えんるんじゃないかというところ。とっくにやってる？
Fisher情報行列はスコア関数の共分散だからテプリッツ行列。だから行けるんじゃね？
ん？他にも共分散行列の高速推定手法を提案してる: