特異値分解
\(M \times N\)の行列\(A\)を以下の3つに分解する。
- \(M \times M\)の直行行列\(V\)
- \(M \times N\)の対角行列\(S\)
- \(N \times N\)の直行行列\(U\)
以下みたいな感じに分解するのが特異値分解。
\begin{eqnarray}
A &=& VSU^T \\
&=&
\begin{pmatrix}
v_{11} & \cdots & v_{1M} \\
\vdots & \ddots & \vdots \\
v_{M1} & \cdots & v_{MM}
\end{pmatrix}
\begin{pmatrix}
\lambda_1 & \cdots & 0 \\
\vdots & \ddots & \vdots \\
0 & \cdots & \lambda_r \\
& & & 0 & \\
& & & & 0
\end{pmatrix}
\begin{pmatrix}
u_{11} & \cdots & u_{N1} \\
\vdots & \ddots & \cdots \\
u_{1N} & \cdots & u_{NN}
\end{pmatrix}
\end{eqnarray}
\(V\)は列ベクトル\(v_1\),\(v_2\),\(\cdots\),\(v_M\)を横に並べたもの。
\(U^T\)は列ベクトル\(u_1\),\(u_2\),\(\cdots\),\(u_N\)を横に並べたものの転値。
\(A\)のランクは\(r\)で、\(S\)は\(r\)個の\(\lambda\)からなる対角行列。
\(\lambda_i\)は対角行列なので対角の非ゼロの項だけ残す意味で以下のようにかける。
\(\lambda_i\)自体はスカラだから前に寄せられる。
\begin{eqnarray}
A = \sum_{i=1}^{r} \lambda_i v_i u_i^T
\end{eqnarray}
特異値分解のやり方
やりたいことは、\(v_i\)、\(u_i\)、\(\lambda_i\)を求めること。
\(AA^T\)、\(A^TA\)の固有値、固有ベクトルを計算することで求まる。
主成分分析の対象とするとき、\(A\)が縦長の行列であることが多い、
つまり高次元のベクトルであることが多いという事実から、
\(AA^T\)は巨大な行列となり、直接計算することは困難。
以下みたいに\(AA^T\)を計算する。
\begin{eqnarray}
AA^T &=& VSU^T(VSU^T)^T \\
&=& VSU^T US^T V^T \\
&=& VSS^TV^T \\
&=& VS_M^2 V^T
\end{eqnarray}
右から\(V\)をかける。
\begin{eqnarray}
AA^T V &=& VS_M^2 \\
AA^T v_i &=& \lambda_i^2 v_i
\end{eqnarray}
これは、\(AA^T\)を固有値\(\lambda_i^2\)、固有ベクトル\(v_i\)に分解した形。
(固有値、固有ベクトルは計算できる)。
同様にして、\(A^TA\)を計算する。
\(A^TA\)の固有値、固有ベクトルの計算により\(u_i\)と\(\lambda_i\)を求められる。
\begin{eqnarray}
A^TA &=& (VSU^T)^T VSU^T \\
&=& US_N^TS_nU^T \\
&=& US_N^2 U^T \\
(A^TA) U &=& US_N^2 \\
(A^TA) u_i &=& \lambda_i^2 u_i
\end{eqnarray}
\(AA^T\)と異なり、\(A^TA\)は大きくなく、容易に計算が可能。
\(v_i\)の求め方
\(AA^T v_i = \lambda_i^2 v_i\)は大きすぎて計算できないが、\(A^TA\)を使って\(AA^T\)を計算できる。
以下のように式変形する。\(u_k\)の正規直行性を使う。
\begin{eqnarray}
A &=& \sum_{i=1}^{r} \lambda_i v_i u_i^T \\
Au_k &=& \sum_{i=1}^{r} \lambda_i v_i u_i^T u_k \\
&=& \lambda_k v_k u_k ^T u_k \\
&=& \lambda_k v_k \\
v_k &=& \frac{1}{\lambda_k} Au_k
\end{eqnarray}
\(A^TA\)の特異値分解は計算可能。以下から\(\hat{u_i}\)と\(\hat{\lambda_i}\)が求まる。
\begin{eqnarray}
(A^TA) \hat{u_i} &=& \hat{\lambda}_i^2 \hat{u_i}
\end{eqnarray}
得られた\(\hat{u_i}\)と\(\hat{\lambda_i}\)を
\(v_k = \frac{1}{\lambda_k} Au_k\)に入れることで、\(v_k\)が求まる。