行列分解(Matrix factorization)まとめ① 〜特異値分解(SVD)〜

特異値分解(SVD; singular value decomposition)は行列を分解する手法の一つで、$n \times n$の行列にとどまらず$m \times n$の行列に用いることができます。当記事では特異値分解や関連する行列分解の手法に関して取りまとめを行いました。

特異値分解

特異値分解の概要

$$
\large
\begin{align}
\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{*}
\end{align}
$$

$m$行$n$列の行列$\mathbf{A}$に対して$m$行$m$列の$\mathbf{U}$、$m$行$n$列の$\mathbf{\Sigma}$、$m$行$n$列の$\mathbf{V}^{*}$を用いて上記のような分解を考えることができる。これを行列$\mathbf{A}$の特異値分解という。

ここで$\mathbf{\Sigma}$は$i$行$i$列の対角成分のみが値を持ち、他の値が$0$の行列である。また、$\mathbf{V}^{*}$は$\mathbf{V}$の随伴行列であるが、ここでは実数のみを考えることから以下転置行列の$\mathbf{V}^{T}$で表す。

$n \times n$対称行列の固有値分解

$n \times n$対称行列(square matrix)の$\mathbf{B}$に関して固有値分解を行うことを考える。まず、$n \times n$の単位行列を$\mathbf{I}_n$とおき、$\det(\mathbf{B}-\lambda \mathbf{E})$の相異なる解を値の大きい順に並べたものを$\lambda_1, \lambda_2, …, \lambda_n$のようにおく。このとき、$\lambda_i$は行列$\mathbf{B}$の固有値であり、$\lambda_i$に対応する固有ベクトルを$\mathbf{u}_i$のようにおくと固有値・固有ベクトルの定義より下記の式が成立する。
$$
\large
\begin{align}
\mathbf{B} \mathbf{u}_i = \lambda_i \mathbf{u}_i
\end{align}
$$

ここで固有値$\lambda_i$と固有ベクトル$\mathbf{u}_i$を用いて下記のように行列$\mathbf{\Lambda}, \mathbf{U}$を定義する。
$$
\large
\begin{align}
\mathbf{\Lambda} &= \left(\begin{array}{ccc} \lambda_{1} & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_{n} \end{array} \right) \\
\mathbf{U} &= \left(\begin{array}{ccc} \mathbf{u}_{1} & … & \mathbf{u}_{n} \end{array} \right)
\end{align}
$$

上記の$\mathbf{U}$は直交行列であり、$\mathbf{U}^{\mathrm{T}} \mathbf{U} = \mathbf{I}_{n}$が成立する。$\mathbf{U}$が直交行列となることは下記で詳しく取り扱った。

対称行列(symmetric matrix)の固有値と固有ベクトルの性質とその導出

このとき、$\mathbf{B}, \mathbf{\Lambda}, \mathbf{U}$に関して下記が成立する。
$$
\large
\begin{align}
\mathbf{B} \mathbf{U} &= \mathbf{U} \mathbf{\Lambda} \\
\mathbf{B} &= \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{-1} \\
&= \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\mathrm{T}}
\end{align}
$$

$n \times n$対称行列$\mathbf{B}$の固有値分解は上記のように行うことができる。本稿の主題である特異値分解はこの固有値分解の拡張で理解することができる。

$\mathbf{A} \mathbf{A}^{\mathrm{T}}$・$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の計算

$m$行$n$列の行列$\mathbf{A}$に対して$\mathbf{A} \mathbf{A}^{\mathrm{T}}$を考えるとこれは$m$行$m$列の対称行列となる。また、$\mathbf{A}^{\mathrm{T}} \mathbf{A}$を考えるとこれは$n$行$n$列の対称行列となる。

$$
\large
\begin{align}
\mathbf{A} = \left(\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{array} \right)
\end{align}
$$
以下、上記のように$3$行$2$列で定義した$\mathbf{A}$を元に$\mathbf{A} \mathbf{A}^{\mathrm{T}}$と$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の行列をそれぞれ確認する。

・$\mathbf{A} \mathbf{A}^{\mathrm{T}}$
$$
\large
\begin{align}
\mathbf{A} \mathbf{A}^{\mathrm{T}} &= \left(\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{array} \right) \left(\begin{array}{cc} a_{11} & a_{21} \\ a_{12} & a_{22} \\ a_{13} & a_{23} \end{array} \right) \\
&= \left(\begin{array}{cc} a_{11}^2+a_{12}^2+a_{13}^2 & a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23} \\ a_{21}a_{11}+a_{22}a_{12}+a_{23}a_{13} & a_{11}^2+a_{12}^2+a_{13}^2 \end{array} \right) \\
&= \left(\begin{array}{cc} a_{11}^2+a_{12}^2+a_{13}^2 & a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23} \\ a_{11}a_{21}+a_{12}a_{22}+a_{13}a_{23} & a_{21}^2+a_{22}^2+a_{23}^2 \end{array} \right)
\end{align}
$$

・$\mathbf{A}^{\mathrm{T}} \mathbf{A}$
$$
\large
\begin{align}
\mathbf{A}^{\mathrm{T}} \mathbf{A} &= \left(\begin{array}{cc} a_{11} & a_{21} \\ a_{12} & a_{22} \\ a_{13} & a_{23} \end{array} \right) \left(\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end{array} \right) \\
&= \left(\begin{array}{ccc} a_{11}^2+a_{21}^2 & a_{11}a_{12}+a_{21}a_{22} & a_{11}a_{13}+a_{21}a_{23} \\ a_{12}a_{11}+a_{22}a_{21} & a_{12}^2+a_{22}^2 & a_{12}a_{13}+a_{22}a_{23} \\ a_{13}a_{11}+a_{23}a_{21} & a_{13}a_{12}+a_{23}a_{22} & a_{13}^2+a_{23}^2 \end{array} \right) \\
&= \left(\begin{array}{ccc} a_{11}^2+a_{21}^2 & a_{11}a_{12}+a_{21}a_{22} & a_{11}a_{13}+a_{21}a_{23} \\ a_{11}a_{12}+a_{21}a_{22} & a_{12}^2+a_{22}^2 & a_{12}a_{13}+a_{22}a_{23} \\ a_{11}a_{13}+a_{21}a_{23} & a_{12}a_{13}+a_{22}a_{23} & a_{13}^2+a_{23}^2 \end{array} \right)
\end{align}
$$

上記の例では$\mathbf{A}$に対して$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$がそれぞれ対称行列となることが確認できる。

また、ここで考えた$m$行$n$列の行列$\mathbf{A}$に対する$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$はどちらも半正定値行列である。このことは任意の$m$次元ベクトル$\displaystyle \mathbf{x} = \left(\begin{array}{c} x_{1} \\ \vdots \\ x_{m} \end{array} \right)$と$n$次元ベクトル$\displaystyle \mathbf{y} = \left(\begin{array}{c} y_{1} \\ \vdots \\ y_{n} \end{array} \right)$に対して下記が成立することよりそれぞれ確認できる。
$$
\large
\begin{align}
\mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{A}^{\mathrm{T}} \mathbf{x} &= (\mathbf{A}^{\mathrm{T}}\mathbf{x})^{\mathrm{T}} (\mathbf{A}^{\mathrm{T}} \mathbf{x}) \geq 0 \\
\mathbf{y}^{\mathrm{T}} \mathbf{A}^{\mathrm{T}} \mathbf{A} \mathbf{y} &= (\mathbf{A}\mathbf{y})^{\mathrm{T}} (\mathbf{A}\mathbf{y}) \geq 0
\end{align}
$$

半正定値行列の固有値

半正定値行列の固有値は非負である。

前項で示した$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$が半正定値行列であることより、$\mathbf{A} \mathbf{A}^{\mathrm{T}}, \mathbf{A}^{\mathrm{T}} \mathbf{A}$の固有値は非負であることを示すことができる。

また、分散共分散行列に関しても$\mathbf{x}^{\mathrm{T}} \mathbf{X}^{\mathrm{T}} \mathbf{X} \mathbf{x} = (\mathbf{X} \mathbf{x})^{\mathrm{T}} (\mathbf{X} \mathbf{x}) \geq 0$のような表し方ができることから、半正定値行列であることが確認できる。

分散共分散行列の数式表現の詳細はPCAの解説の際に関連で取り扱ったので、合わせてご確認ください。

以下、半正定値行列の固有値が非負であることを示す。

$n \times n$対称行列の固有値分解の内容に基づいて$\mathbf{B}=\mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\mathrm{T}}$と表せると考えるとき、$\mathbf{x}^{\mathrm{T}}\mathbf{B}\mathbf{x}$は下記のように変形することができる。
$$
\large
\begin{align}
\mathbf{x}^{\mathrm{T}}\mathbf{B}\mathbf{x} &= \mathbf{x}^{\mathrm{T}} \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\mathrm{T}} \mathbf{x} \\
&= (\mathbf{U}^{\mathrm{T}} \mathbf{x})^{\mathrm{T}} \mathbf{\Lambda} (\mathbf{U}^{\mathrm{T}} \mathbf{x})
\end{align}
$$

ここで上記の式における$\mathbf{U}^{\mathrm{T}} \mathbf{x}$を$\mathbf{y} = \mathbf{U}^{\mathrm{T}} \mathbf{x}$のようにおくことを考える。このとき$\mathbf{y}^{\mathrm{T}}\mathbf{\Lambda}\mathbf{y} = \mathbf{x}^{\mathrm{T}}\mathbf{B}\mathbf{x} \geq 0$が成立するが、$\mathbf{\Lambda}$が対角行列であることから$\mathbf{\Lambda}$の全ての値が$0$以上でなければ$\mathbf{y}^{\mathrm{T}}\mathbf{\Lambda}\mathbf{y} \geq 0$は成立しない。

よって半正定値行列の固有値は非負であると考えることができる。

特異値分解の導出

$$
\large
\begin{align}
\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}
\end{align}
$$

行列$\mathbf{A}$が上記のように表すことができるとき、直交行列$\mathbf{U}$と$\mathbf{V}$はそれぞれ$\mathbf{A} \mathbf{A}^{\mathrm{T}}$、$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の固有ベクトルに基づく行列であることを以下に示す。

$$
\large
\begin{align}
\mathbf{A} \mathbf{A}^{\mathrm{T}} &= (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}) (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}})^{\mathrm{T}} \\
&= \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}} \mathbf{V} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{U}^{\mathrm{T}} \\
&= \mathbf{U} \mathbf{\Sigma} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{U}^{\mathrm{T}}
\end{align}
$$

$$
\large
\begin{align}
\mathbf{A}^{\mathrm{T}} \mathbf{A} &= (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}})^{\mathrm{T}} (\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}) \\
&= \mathbf{V} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{U}^{\mathrm{T}} \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}} \\
&= \mathbf{V} \mathbf{\Sigma}^{\mathrm{T}} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}}
\end{align}
$$

上記を$n \times n$対称行列の固有値分解の式と同様に考えることで$\mathbf{U}$が$\mathbf{A} \mathbf{A}^{\mathrm{T}}$の固有ベクトルに基づく行列であり、$\mathbf{V}$が$\mathbf{A}^{\mathrm{T}} \mathbf{A}$の固有ベクトルに基づく行列であることがわかる。

SVDと行列のノルム

行列のpノルム(p-norm)の定義・計算方法・計算例の確認

上記などを参考に行列$\mathbf{A} \in \mathbb{R}^{m \times n}$のフロベニウスノルムを$||\mathbf{A}||_{F}$、$2$-normを$||\mathbf{A}||_{2}$とおく。このときSVDにおける対角行列(diagonal matrix)$\mathbf{\Sigma} = \mathrm{diag}(\sigma_{1}, \cdots \sigma_{p}), \, p = \min{(m, n)}$の最大成分を$\sigma_{\max}$とおくと、$||\mathbf{A}||_{F}$と$||A||_{2}$は下記のように表される。
$$
\large
\begin{align}
|\mathbf{A}||_{F} &= \sqrt{\sigma_{1}^{2} + \cdots \sigma_{p}^{2}} \quad (1) \\
||\mathbf{A}||_{2} &= \sigma_{\max} \quad (2)
\end{align}
$$

フロベニウスノルムについては次節でも取り扱った。

$(1)$式の導出

$\mathbf{A}=\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}$の$\mathbf{U}$と$\mathbf{V}$が直交行列であることから下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{F} &= ||\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}||_{F} \\
&= ||\mathbf{\Sigma}||_{F}
\end{align}
$$

ここで$\mathbf{\Sigma}=\mathrm{diag}(\sigma_{1}, \cdots \sigma_{p})$より下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{F} &= ||\mathbf{\Sigma}||_{F} \\
&= \sqrt{\sigma_{1}^{2} + \cdots \sigma_{p}^{2}} \quad (1)
\end{align}
$$

$(2)$式の導出

$\mathbf{A}=\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}$の$\mathbf{U}$と$\mathbf{V}$が直交行列であることから下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{2} &= ||\mathbf{U} \mathbf{\Sigma} \mathbf{V}^{T}||_{2} \\
&= ||\mathbf{\Sigma}||_{2}
\end{align}
$$

ここで$2$-normの定義より下記が成立する。
$$
\large
\begin{align}
||\mathbf{A}||_{2} &= ||\mathbf{\Sigma}||_{2} \\
&= \sigma_{\max} \quad (2)
\end{align}
$$

特異値分解の近似

前節では固有値分解の考え方に基づいて特異値分解の導出を確認したが、行列の行数や列数が大きい場合は固有値や固有ベクトルの計算が複雑になり、同様の計算を行うのは難しい。したがって実際に行列の分解を行うにあたっては近似的な手法が基本的に用いられる。

近似を考える際は$\mathbf{A}$の分解した行列を元に$\mathbf{A}$をどのくらい復元できるかと考えることで近似を評価すると考えれば良い。以下ではフロベニウスノルムによって近似を評価し、これに対して勾配法を適用することによって分解を行うベーシックな手順について取りまとめる。

フロベニウスノルム(Frobenius norm)

特異値分解の近似を考えるにあたっては、$\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^{\mathrm{T}} = \mathbf{U}’ \mathbf{V}’$のような分解に対し、行列ノルムの$||\mathbf{A}-\mathbf{U}’ \mathbf{V}’||$を考え、与えられた$\mathbf{A}$に対してノルムを最小にするように$\mathbf{U}’, \mathbf{V}’$を繰り返し演算によって計算すれば良い。

このように行列のノルムを考える際のシンプルな考え方がフロベニウスノルム(Frobenius norm)である。$m$行$n$列の行列$\mathbf{A} = (a_{ij})$に関するフロベニウスノルム$|\mathbf{A}|_{F}$は下記のように定義できる。
$$
\large
\begin{align}
||\mathbf{A}||_{F} = \sqrt{ \sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}^2 }
\end{align}
$$

フロベニウスノルムは行列の各要素の二乗の和を計算し、計算した二乗和に対して平方根を考えた値に一致する。フロベニウスノルムはヒルベルト＝シュミットノルム(Hilbert–Schmidt norm)ともいわれることも抑えておくと良い。

上記のフロベニウスノルムの定義から二つの行列$\mathbf{X}, \mathbf{Y}$の差の大小を考えるにあたって、$||\mathbf{X}-\mathbf{Y}||_{F}^{2}$を用いて考えることは妥当であると思われる。

勾配降下法による近似

前項までの内容を元に考えると、$||\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}||_{F}^{2}$を最小にする$\mathbf{\tilde{U}}, \mathbf{\tilde{V}}$を計算することで特異値分解を行うことができることがわかる。

$\mathbf{\tilde{U}}$全体に関する勾配を$\nabla_{\mathbf{\tilde{U}}} ||\mathbf{A}-\mathbf{\tilde{U}}\mathbf{\tilde{V}}||_{F}^{2}$とおくと、$\nabla_{\mathbf{U}’} ||\mathbf{A}-\mathbf{\tilde{U}} \mathbf{\tilde{V}}||_{F}^{2}$は下記のように計算できる。
$$
\large
\begin{align} \nabla_{\mathbf{\tilde{U}}} ||\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}||_{F}^{2} = -(\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}) \mathbf{\tilde{V}}^{\mathrm{T}}
\end{align}
$$

同様に$\mathbf{\tilde{V}}$全体に関する勾配を$\nabla_{\mathbf{\tilde{V}}} ||\mathbf{A}-\mathbf{\tilde{U}}\mathbf{\tilde{V}}||_{F}^{2}$とおくと、$\nabla_{\mathbf{\tilde{V}}} ||\mathbf{A}-\mathbf{\tilde{U}} \mathbf{\tilde{V}}||_{F}^{2}$は下記のように計算できる。
$$
\large
\begin{align} \nabla_{\mathbf{\tilde{V}}} ||\mathbf{A}-\mathbf{\tilde{U}}
\mathbf{\tilde{V}}||_{F}^{2} = -\mathbf{A}^{\mathrm{T}} \mathbf{\tilde{U}} + \mathbf{\tilde{V}} \mathbf{\tilde{U}}^{\mathrm{T}} \mathbf{\tilde{U}}
\end{align}
$$

上記の導出は「関係データ学習」の$4.4.1$節の「$1$次交互勾配降下法」で取り扱われているので、詳しくはそちらを参照ください。

$l^{2}$正則化と勾配降下法

参考

・実$2$次形式と正定値行列
https://www.chaos.cs.tsukuba.ac.jp/ila/chapter5.pdf
・特異値分解とその応用
https://www.chaos.cs.tsukuba.ac.jp/ila/chapter7.pdf
・関係データ学習