【丁寧に解説します】特異値分解の計算方法

本日はディープラーニングe資格でもお馴染みの特異値分解の計算方法をstep by stepで解説してみたいと思います。

特異値分解とは任意の$m \times n$の行列$A$を$A = UΣV^T$ ($U$は$m \times m$の直交行列、$V$は$n \times n$の直交行列）のように分解することです。このように分解することで、行列$A$の主要な構成要素を抽出することができる、つまり重要でない要素を捨てて次元削減することができるというのが実用上の意義です。

しかし、今回は特異値分解の本質的な意義には立ち入らず、行列$U,Σ,V$を求めるための計算方法に焦点を当てて説明したいと思います。たかが計算ですが、しっかりやろうとすると意外と手間がかかるので、本記事が皆さんの理解のお役に立てば幸いです。

今回は$ A = \begin{pmatrix} 1 & 1& 0 \\ 1 & 0 & 1 \\ \end{pmatrix}$という行列を題材にして計算過程を説明していきます。

【給付金で70%OFF】AI・データサイエンスの全コンテンツが期間無制限で見放題のキカガク長期コースの無料WEB説明会

まずは行列$Σ$から求めよう

行列$Σ$は$A$と同じく$m \times n$の行列で、対角成分を除いて全て$0$になります。正方行列の対角化のイメージで覚えておくと分かりやすいですね。

ちなみに形状が$m \times n$になることは行列の積の性質を考えると理解することができます。行列$P,Q$の積$PQ$を計算するという場合には、$P$の列数と$Q$の行数は必ず一致していなければなりません。特異値分解の定義から$Σ$は$m \times m$の$U$,$n \times n$の$V^T$との積を計算できることが必要ですから、必然的に形状は$m \times n$に定まります。

さて、$Σ$は対角成分以外は$0$ですから、逆に言えば対角成分さえ求めればよいということになります。先に結論を言ってしまうと、対角成分に入ってくるのは、行列$AA^T$または$A^T A$の固有値のどちらかです。どちらの固有値が入るのかは$Σ$の形状によって以下の規則で決まります。

$m>n$（行列$A$が縦に長い）の場合は$AA^T$のn個の固有値を対角成分にする。

$m<n$（行列$A$が横に長い）の場合は$A^T A$のm個の固有値を対角成分にする。

今回の例は$m<n$であるため、$A^T A$の固有値を計算することになるので、まずは$A^T A$を求めましょう。

$A^T A = \begin{pmatrix} 1 & 1\\ 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1& 0 \\ 1 & 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0& 1\end{pmatrix} $

固有値を$λ$、固有ベクトルを$\vec{v}$とすると、次の数式が成立します。

$\begin{pmatrix} 2 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0& 1\end{pmatrix} \vec{v} = λ \vec{v} \\ \Leftrightarrow \begin{pmatrix} 2-λ & 1 & 1 \\ 1 & 1-λ & 0 \\ 1 & 0& 1-λ\end{pmatrix} \vec{v}= 0$

$\vec{v} \neq 0$なので$det(A^T A – λE) = 0$が成立しなければなりません。$3 \times 3$行列の行列式はサラスの公式から求められるので、結果として次の数式を満たすλを求めることになります。

$(2-λ)(1-λ)^{2}-(1-λ)-(1-λ) = 0$

この方程式を解くと$λ=0,1,3$が得られます。ここまで分かったら次の規則に従って、行列$Σ$の対角成分を埋めていきます。

固有値の正の平方根を降順で$Σ$の対角成分に入れていく

規則としては非常にシンプルですね。この規則に従って固有値を入れると、$Σ$は次のようになります。

$Σ = \begin{pmatrix} \sqrt{3} & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$

次は固有ベクトルを求めよう

さて、ここでもう1つ重要な性質を紹介します。

行列$V$は行列$A^T A$の固有ベクトルを列成分に持つ。

行列$U$は行列$AA^T$の固有ベクトルを列成分に持つ。

現時点で$A^T A$の固有値は分かっていますから、この性質を使って$V$を計算します。固有値$λ=3$の場合は次の数式が成立します。

$\begin{pmatrix} -1 & 1 & 1 \\ 1 & -2 & 0 \\ 1 &0 & -2 \end{pmatrix} \begin{pmatrix} v_1 \\ v_2 \\ v_3 \end{pmatrix} = 0 \Leftrightarrow \begin{align} -v_1 + v_2 + v_3 & = 0 \\ v_1 -2v_2 & = 0 \\ v_1 -2v_3& = 0 \end{align}$

この方程式を解けばよいわけですが、1つだけ注意すべき点があります。それは行列$V$が直交行列であるということです。直交行列であるということは、$V^T V = E$となるはずなので、$ \begin{pmatrix} v_1 \\ v_2 \\ v_3 \end{pmatrix}$のノルム（大きさ）は$1$でなければなりません。この条件を踏まえて方程式を解くと、 $ \begin{pmatrix} \frac{2}{\sqrt{6}} \\ \frac{1}{\sqrt{6}} \\ \frac{1}{\sqrt{6}} \end{pmatrix}$ と求まります。$λ=0,1$の場合も全く同様に計算し、得られたベクトルを並べると、行列$V$は以下のように得られます。

$V = \begin{pmatrix} \frac{2}{\sqrt{6}} & 0 & \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{3}} \end{pmatrix} $

あとは最後の行列を求めるだけ

さて、この計算の目標は$A=UΣV^T$を満たすような、$U,Σ,V$を求めることです。ここまでで$Σ, V$はすでに分かっているので、その情報を利用して$U$を求めましょう。

$A=UΣV^T$ に右から$V$を乗じて、$V^T V = E$（$V$は直交行列）となることを利用すると、$AV=UΣ$が成立します。ここで、$U$は$2 \times 2$の行列であることが分かっているので、$U = \begin{pmatrix} u_{11} & u_{12} \\ u_{21} & u_{22} \end{pmatrix} $とおいて、$A,V,Σ$の中身を代入すると次の数式が成立します。

$\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} \frac{2}{\sqrt{6}} & 0 & \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{3}} \end{pmatrix} = \begin{pmatrix} u_{11} & u_{12} \\ u_{21} & u_{22} \end{pmatrix} \begin{pmatrix} \sqrt{3} & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$

$\Leftrightarrow \begin{pmatrix} \frac{3}{\sqrt{6}} & \frac{1}{\sqrt{2}} & 0 \\ \frac{3}{\sqrt{6}} & -\frac{1}{\sqrt{2}} & 0 \end{pmatrix} = \begin{pmatrix} \sqrt{3}u_{11} & u_{12} & 0 \\ \sqrt{3}u_{21} & u_{22} & 0 \end{pmatrix}$

ここで両辺を比較すると、$U=\begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix}$と求められます。