Method

行列の低ランク近似

テンソルネットワークの基本は，「大きな対象を小さなパーツの積で表す」です．そのもっとも単純な例が，行列に対する行列分解(特異値分解)と低ランク近似です．行列分解とは，ある行列$A$を以下のような行列の積で表す方法です．

A = BCD\cdots

また，低ランク近似とは，行列を，より小さいランクの行列で近似することです．低ランク近似により，行列を保存しておくためのメモリコストを削減できます．行列分解の具体的な方法は，QR分解，LU分解をはじめ多く知られています．ここでは，分解により低ランク近似することを念頭に置き，特異値分解を用いて説明します．

特異値分解

一般の複素行列 $A \in \mathbb{C}^{m \times n}$ に対して，次の関係を満たす非負実数 $\sigma_i$ とベクトル $\mathbf{u}_i, \mathbf{v}_i$ を考えます． $\sigma_i$ を特異値，$\mathbf{u}_i, \mathbf{v}_i$ をそれぞれ左特異ベクトル，右特異ベクトルと呼びます．

\begin{cases} A\mathbf{v}_i = \sigma_i \mathbf{u}_i,\\ A^\dagger \mathbf{u}_i = \sigma_i \mathbf{v}_i. \end{cases}

特異値は大きい順に $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \gt 0$ と並べることにします．ここで $r=\mathrm{rank}(A)$ です．ここではランク落ちしていないサイズ $m \lt n$の横長行列を例にし， $r=m$ とします．

U = (\mathbf{u}_1,\dots,\mathbf{u}_r), \qquad V = (\mathbf{v}_1,\dots,\mathbf{v}_r), \qquad \Sigma = \mathrm{diag}(\sigma_1,\dots,\sigma_r)

上記のように，左特異ベクトルを列に並べた行列を $U \in \mathbb{C}^{m \times r}$，右特異ベクトルを列に並べた行列を $V \in \mathbb{C}^{n \times r}$ とすると，行列 $A$ は次のように分解できます．

A = U\Sigma V^\dagger

ここで $\Sigma \in \mathbb{R}^{r \times r}$ であり， $V^\dagger \in \mathbb{C}^{r \times n}$ です．したがって，右辺は $(m \times r)(r \times r)(r \times n)$ の積になっています．これを特異値分解（Singular Value Decomposition: SVD）と呼びます．成分で書くと，

A = \sum_{i=1}^{r} \sigma_i \mathbf{u}_i \mathbf{v}_i^\dagger

となります．つまり，行列 $A$ はランク 1 行列 $\mathbf{u}_i \mathbf{v}_i^\dagger$ の和として表されています．

SVDによる低ランク近似

特異値が大きい項ほど，行列 $A$ の中で支配的な寄与を持ちます．そのため，十分小さい特異値に対応する項を捨てることで，元の行列をより低いランクの行列で近似できます． $\chi (\lt r)$ 個の特異値だけを残すと，

\widetilde{A}_{\chi} = \sum_{i=1}^{\chi} \sigma_i \mathbf{u}_i \mathbf{v}_i^\dagger = \widetilde{U}\widetilde{\Sigma}\widetilde{V}^\dagger

というランク $\chi$ の近似行列が得られます．分解後の行列サイズは， $\widetilde{U} \in \mathbb{C}^{m \times \chi}$， $\widetilde{\Sigma} \in \mathbb{R}^{\chi \times \chi}$， $\widetilde{V}^{\dagger} \in \mathbb{C}^{\chi \times n}$ です．

SVD による低ランク近似のイメージ．横長かつフルランクな行列を想定しているため，上段では $r=m$ であり，$U$ と $\Sigma$ は正方形に描いている．下段では $\chi \lt r$ 個の特異値だけを残している．

SVD による切り捨ては，フロベニウスノルムの意味で最良の低ランク近似を与えることが知られています(Eckart-Young-Mirskyの定理)．すなわち，ランクが $\chi$ 以下の行列 $B$ の中で， $\|A-B\|_{\mathrm{F}}$ を最小にするものが $\widetilde{A}_{\chi}$ です．その誤差は，捨てた特異値の平方和で表されます．

\|A-\widetilde{A}_{\chi}\|_{\mathrm{F}}^2 = \sum_{i=\chi+1}^{r}\sigma_i^2.

また，$m\times n$ 行列をそのまま保存すると必要な要素数は $mn$ ですが， $\chi$ 個の特異値だけを残す近似では，おおよそ $\chi(m+n+1)$ 個の要素を保存すればよくなります．そのため，

mn \gt \chi(m+n+1)

が成り立つ範囲では，低ランク近似によってデータ量を削減できます．

テンソルネットワークへの接続

テンソルネットワークでは，高次元テンソルを適切に行列化し， SVD のような低ランク近似を繰り返し使うことで，複数の小さなテンソルの縮約として表します．行列で見た「重要な成分だけを残す」という考え方が，テンソルネットワークの基本的な圧縮原理になっています．

次はテンソル分解のページで，行列の低ランク近似を高階テンソルへ拡張します．