カテゴリー: 線形代数

[mathjax] 特異値分解 (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)に分解した形。 (固有値、固有ベクトルは計算できる)。 [clink url=\"https://ikuty.com/2019/06/17/eigenvalue-eigenvector/\"] 同様にして、(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)が求まる。

[mathjax] 線形代数もやりなおします。流石に時間ないので微妙に分かるところまでですが。 第1弾は固有値、固有ベクトル。 具体例を使って追ってみるやつ 行列(A)とベクトル(vec{v_1})をデタラメに選んで内積を取ってみる。 (A=begin{pmatrix} 2 & 5 \\ 3 & 7 end{pmatrix})。(vec{v_1}=begin{pmatrix} 1 \\ 4end{pmatrix})。 begin{eqnarray} vec{v_2} = Avec{v} = begin{pmatrix} 2 & 5 \\ 3 & 7 end{pmatrix} begin{pmatrix} 1 \\ 4end{pmatrix} = begin{pmatrix} 2 times 1 + 5 times 4 \\ 3 times 1 + 7 times 4 end{pmatrix} = begin{pmatrix} 22 \\ 31 end{pmatrix} end{eqnarray} (vec{v_1})と(vec{v_2})は向きが違うし大きさも違う。 (vec{v_1})に(A)をかけることで、回転して伸ばしてる。 (vec{v_1})と(vec{v_2})の向きが同じになるように(vec{v_1})を選べないか...。 下みたいな組み合わせだと、左と右が同じ向きになる。 begin{eqnarray} begin{pmatrix} 2 & 5 \\ 3 & 7 end{pmatrix} begin{pmatrix}0.575249 \\ 0.817978end{pmatrix} = begin{pmatrix}5.2403 \\ 7.4515end{pmatrix} end{eqnarray} 伸ばす分を外に出すと以下みたいになる。 begin{eqnarray} begin{pmatrix} 2 & 5 \\ 3 & 7 end{pmatrix} begin{pmatrix}0.575249 \\ 0.817978end{pmatrix} = 9.10977 begin{pmatrix}0.575249 \\ 0.817978end{pmatrix} end{eqnarray} 長さを伸ばす分の係数(9.10977)が行列(A)の固有値。 begin{pmatrix}0.575249 \\ 0.817978end{pmatrix}が行列(A)の固有ベクトル。 次数が多いやつ (A)は(n times n)の正方行列。固有ベクトル(vec{x})は(1 times n)。固有値(lambda)はスカラー。 begin{eqnarray} A vec{x} &=& lambda vec{x} end{eqnarray} 以下みたいに変形して(vec{x})と(lambda)を求める。 begin{eqnarray} (A-lambda E) vec{x} &=& vec{0} end{eqnarray} ((A-lambda E))に逆行列があると(Evec{x} = vec{0})とかになってゼロベクトルじゃない(vec{x})を求められないから、 逆行列が存在しない、という式を立てるらしい。。 \"逆行列が存在しない\"だけだと、(vec{x})も(lambda)も複数ありそうだけど絶対に1つしか存在しないらしい。 逆行列が存在しないのは、行列式がゼロ、とするらしい。 begin{eqnarray} det(A-lambda E) = 0 end{eqnarray} 手計算が合わないのでそれ以降は省略... まとめ 行列(A)の固有値、固有ベクトルは、 (A vec{x} = lambda vec{x})となる(vec{x})と(lambda)のセットを求めることでした。 向き、大きさの変換を表す(A)を、向きを表すベクトル(vec{x})と大きさ(lambda)で表しなおす..ような。