テンソルネットワークを学ぶ上で基本となるのが特異値分解です。
この記事では特異値分解(SVD)とその応用である低ランク近似(LRA)について、自分用に簡単にまとめておきます。
特異値分解 (Singular Value Decomposition)
特異値分解(SVD)とは、任意のm行n列の行列M（rank R)を次のように3つの行列に分解することです。
M = UΣV^{\dagger}
Vはm行m列、Uはn行n列のユニタリ行列です。またΣはm行n列の対角行列です。Σの対角成分は行列Mの特異値と呼び、R個の非負の実数が並んだ対角行列です。
上式を成分表示でも書いておきます。(特異値は小文字のσを使います)
M_{ij} = \sum_{k=1}^{R}U_{ik}\sigma_{k}V_{jk}^{*}
任意の行列Mが一意なΣを用いて分解できるのが味噌です。(UとVは一意でない)
低ランク近似 (Low-Rank Approximation)
低ランク近似(LRA)は、先ほどの行列MをSVDした後に行います。例えば行列MにSVDを施し、特異値σ(R個)を大きな値から順に得たとします。小さな特異値の値がほとんど0である時、それを捨ててしまうことを低ランク近似と言います。あるS番目からR番目まで(S<R)特異値を捨てるとして、成分表示で上記の操作を書くと、
M=\sum_{k=1}^{R}U_{ik}\sigma_{k}V_{jk}^{*}\simeq\sum_{k=1}^{S}U_{ik}\sigma_{k}V_{jk}^{*}=\widetilde{M}
となります。近似の際に元のrank Rからrank Sへ落ちるのでLRAと呼ぶわけです。
近似された行列$\widetilde{M}$と元の行列$M$の間にどの程度エラーがあるのか、全成分の絶対二乗誤差を計算することで評価してみます。
\begin{align*}
\sum_{i,j}|M_{ij} - \widetilde{M_{ij}}|^2 &= \sum_{i,j}(M_{ij} - \widetilde{M_{ij}})(M_{ij} - \widetilde{M_{ij}})^{*} \\
&= \sum_{i,j}(\sum_{k=S+1}^{R}U_{ik}\sigma_{k}V_{jk}^{*})(\sum_{k'=S+1}^{R}U_{ik'}\sigma_{k'}V_{jk'}^{*})^{*} \\
&= \sum_{k=S+1}^{R}\sum_{k'=S+1}^{R}\sigma_{k}\sigma_{k'}\sum_{i}U_{ik}U_{ik'}^
{*}\sum_{j}V_{jk}^{*}V_{jk'} \\
&= \sum_{k=S+1}^{R}\sum_{k'=S+1}^{R}\sigma_{k}\sigma_{k'}\delta_{kk'}\delta_{kk'} \\
&= \sum_{k=S+1}^{R}\sigma_{k}^2
\end{align*}
よって「全成分の絶対二乗誤差は、捨てた特異値の2乗和と等しい」ことが分かります。(Eckart-Youngの定理を参照)