正定値対称行列$A\in {\mathbb R}^{n\times n}$に対して、$A=RR^\top$なる下三角行列$R\in {\mathbb R}^{n\times n}$が存在します(この証明は省略します)。成分で書くと
$$ A_{ji}=\sum_{h=1}^nR_{jh}R_{ih},\hspace{5mm}i,j=1,\ldots,n$$ が成立します。最初に$R_{ij}$, $i,j=1,\ldots,n$ をすべて0にしてから、各$i=1,\ldots,n$で
1. $R_{ii}=\sqrt{A_{ii}-\sum_{h=1}^{i-1}R_{ih}^2}$
2. $R_{ji}=(A_{ji}-\sum_{h=1}^{i-1}R_{jh}R_{ih})/R_{ii}$, $\hspace{3mm}j=i+1,\ldots,n$
によって、$R$の第$i$列が求まります。2.は$(n-i)^2$回の演算(乗算)が必要で、全体で
$$\sum_{i=1}^n(n-i)^2=\sum_{j=0}^{n-1}j^2=\frac{1}{6}(n-1)n(2(n-1)-1)=\frac{n^3}{3}(1-\frac{1}{n})(1-\frac{1}{2n})$$回、高々$n^3/3$の演算が必要です。他方、$A,B\in {\mathbb R}^{n\times n}$の乗算は、その第$i,j$成分が$\sum_{h=1}^n A_{ih}B_{hj}$によって得られ、この操作を$n^2$個の成分すべてに対して行うので、$n^3$回の演算が必要です。$A$の逆行列を求める操作も同様の時間を要します。
計算量のオーダー表現は、定数倍の差異を除いて考えるので、上記すべて$O(n^3)$という表記が本来ですが、機械学習のためのカーネル6.1節では、$O(n^3/3)$, $O(n^3)$というように両者を区別しています。
また、下三角行列$L\in {\mathbb R}^{n\times n}$とある定数ベクトル$b\in {\mathbb R}^{n}$があって、$Lx=b$なる$x$を求めるためには、$$x_i=(b_i-\sum_{h=1}^{i-1}L_{i,j}x_j)/L_{ii}$$を各$i=1,\ldots,n$に対して行う必要があり、高々$1+\ldots+(n-1)=n(n-1)/2$回の乗算が必要です。テキストではこれを$O(n^2)$の時間がかかるとしています。
数学で記述できます。「統計的機械学習の数理100問with R」は、数学の各段階をソースコードで正確に書いて、動作を確認しています。このようにすると、自然と数学的なロジックもついてきて、データサイエンスに必要な本質を見る姿勢ができてきます。業務でパッケージを用いることは否定しません。しかし、勉強の段階では、ブラックボックスにしないで、動作を確認すべきです。そして、正しい結論を世の中に提供するという本来の使命を果たすべきだと思っています。
