応用上よく使われる特異値分解(singular value decomposition ; SVD)について,どのように導出するのか,左特異ベクトル,特異値,右特異ベクトルがいったい何なのかという点にいつもモヤモヤしてしまうので,その内容を調べてまとめることにしました.

文献[1]の3章をベースにしてまとめますが,行間を埋めるための説明や式変形の途中経過を追加しています.また定理の証明を省略している箇所があります.

=================================================================================
特異値分解は複素数を要素にもつ行列に対する概念ですが,本記事で扱う行列,ベクトルの要素はすべて実数であるとします.

[ 1. 最良の部分空間 ]
{displaystyle mathrm{rank}A=r }{displaystyle n 	imes d } 実行列 {displaystyle A } の行ベクトルを {displaystyle d } 次元空間における {displaystyle n } 個の点と解釈し,それらの点の集合についての最良の {displaystyle k  (le r) } 次元部分空間を見つけることを考えます.“最良”とは,{displaystyle n } 個の各点から部分空間へ(直交する方向)の距離の二乗の総和が最小となることを意味します.

簡単化のため,部分空間が {displaystyle 1 } 次元空間,すなわち原点を通る直線の場合を考えます.空間上の点の集合 {displaystyle { oldsymbol{a}_i }_{i=1,cdots,n},  oldsymbol{a}_i in mathbb{R}^d } に対して最もあてはまりのよい原点を通る直線を探すことは,点から直線へ(直交する方向)の距離の二乗の総和を最小化すること,すなわち最良の {displaystyle 1 } 次元部分空間を見つけることを意味します.{displaystyle oldsymbol{a}_i = ( a_{i1}, cdots, a_{id} )^T } から原点を通る直線へ射影することを考えると,三平方の定理より以下が成り立ちます.

(1.1){displaystyle ;;;  a_{i1}^2 + a_{i2}^2 + cdots + a_{id}^2 =  (mathrm{射影の長さ}_i)^2 + (mathrm{点から直線への距離}_i)^2 }

したがってすべての点について考えると以下が成り立ちます.

(1.2){displaystyle ;;; sum_{i=1}^n(mathrm{点から直線への距離}_i)^2 = sum_{i=1}^n ( a_{i1}^2 + a_{i2}^2 + cdots + a_{id}^2 ) - sum_{i=1}^n (mathrm{射影の長さ}_i)^2  }

最良の {displaystyle 1 } 次元部分空間を見つけるためには,右辺第一項は定数なので {displaystyle (mathrm{点から直線への距離}_i)^2 } の総和を最小化する,すなわち {displaystyle (mathrm{射影の長さ}_i)^2 } の総和を最大化すればよいことがわかります.

同様に,最良の {displaystyle k } 次元部分空間を見つけるためにはその部分空間への射影を考え,{displaystyle (mathrm{射影の長さ}_i)^2 } の総和を最大化すればよいことになります.ここまでで,最良の {displaystyle k } 次元部分空間の意味とその導出のための手がかりが明らかになりました.次の章ではその部分空間の基底を導出していきます.



[ 2. 右特異ベクトルと特異値の導出 ]
{displaystyle n 	imes d } 実行列 {displaystyle A  (mathrm{rank}A = r) } の要素からなる {displaystyle d 	imes 1 } ベクトル {displaystyle oldsymbol{a}_i,  i=1,ldots,n }

(2.1){displaystyle ;;; A = egin{bmatrix} a_{11} & a_{12} & cdots & a_{1d}  a_{21} & a_{22} & cdots & a_{2d}  vdots & vdots & vdots & vdots  a_{n1} & a_{n2} & cdots & a_{nd} end{bmatrix}= egin{bmatrix} oldsymbol{a}_1^T  oldsymbol{a}_2^T  vdots  oldsymbol{a}_n^T end{bmatrix} }

のように定義し,{displaystyle d } 次元空間における {displaystyle n } 個の点とみなします.その {displaystyle d } 次元空間の原点を通るある直線上の {displaystyle d 	imes 1 } 単位ベクトルを {displaystyle oldsymbol{v}, ||oldsymbol{v}|| =1  } とします. {displaystyle langle cdot , cdot 
angle  } は通常の内積, {displaystyle || cdot|| = ( langle cdot , cdot 
angle )^{1/2} } はユークリッドノルムです.以下を得ることができます.{displaystyle | langle oldsymbol{a}_i ,  oldsymbol{v} 
angle | }{displaystyle oldsymbol{a}_i }{displaystyle oldsymbol{v} } への射影の長さを意味します.

(2.2){displaystyle ;;; A oldsymbol{v} = egin{bmatrix} oldsymbol{a}_1^T  oldsymbol{a}_2^T  vdots  oldsymbol{a}_n^T end{bmatrix} oldsymbol{v} = egin{bmatrix} oldsymbol{a}_1^T oldsymbol{v}  oldsymbol{a}_2^T oldsymbol{v}  vdots  oldsymbol{a}_n^T oldsymbol{v} end{bmatrix} = egin{bmatrix} langle oldsymbol{a}_1 ,oldsymbol{v} 
angle  langle oldsymbol{a}_2 ,oldsymbol{v} 
angle  vdots  langle oldsymbol{a}_n ,oldsymbol{v} 
angle end{bmatrix}   }

(2.3){displaystyle ;;; ||Aoldsymbol{v}|| = sqrt{ | langle oldsymbol{a}_1 ,oldsymbol{v} 
angle |^2 + | langle oldsymbol{a}_2 ,oldsymbol{v} 
angle |^2 + cdots + | langle oldsymbol{a}_n ,oldsymbol{v} 
angle |^2 } }

(2.4){displaystyle ;;; ||Aoldsymbol{v}||^2 = | langle oldsymbol{a}_1 ,oldsymbol{v} 
angle |^2 + | langle oldsymbol{a}_2 ,oldsymbol{v} 
angle |^2 + cdots + | langle oldsymbol{a}_n ,oldsymbol{v} 
angle |^2  }

(2.4)はまさに(1.2)の右辺第二項(の符号反転),すなわち {displaystyle (mathrm{射影の長さ}_i)^2 } の総和に相当します.これを用いて行列 {displaystyle A } の第1右特異ベクトル {displaystyle oldsymbol{v}_1 },第1特異値 {displaystyle sigma_1 } を定義します.{displaystyle oldsymbol{v}_1 } は点の集合 {displaystyle { oldsymbol{a}_i }_{i=1,ldots,n} } の最良の {displaystyle 1 } 次元部分空間,{displaystyle sigma_1^2 }{displaystyle oldsymbol{v}_1 } への射影の長さの二乗の総和です.

(2.5){displaystyle ;;; oldsymbol{v}_1 = mathrm{arg  max}_{{ ||oldsymbol{v}||=1 } } ||A oldsymbol{v}||   }

(2.6){displaystyle ;;; sigma_1(A) = || A oldsymbol{v}_1 || }

次に {displaystyle oldsymbol{v}_1 } を基底(の1つ)とする最良の {displaystyle 2 } 次元部分空間を見つけることを考えます.三平方の定理より,その {displaystyle 2 } 次元部分空間への射影の長さの二乗の総和は, {displaystyle oldsymbol{v}_1 } への射影の長さの二乗の総和と {displaystyle oldsymbol{v}_1 } に直交するベクトルへの射影の長さの二乗の総和“の和”に等しくなります.したがって,{displaystyle oldsymbol{v}_1 } を基底(の1つ)とする最良の{displaystyle 2 } 次元部分空間を見つけるためには,射影の長さ {displaystyle || A oldsymbol{v} ||^2 } を最大にする単位ベクトル {displaystyle oldsymbol{v}=oldsymbol{v}_2,  oldsymbol{v}_2 perp oldsymbol{v}_1 } を見つければよいことになります.第2特異ベクトル {displaystyle oldsymbol{v}_2 },第2特異値 {displaystyle sigma_2 } を定義します.以降の右特異ベクトル {displaystyle oldsymbol{v}_3,ldots,oldsymbol{v}_r } と特異値 {displaystyle sigma_3,ldots,sigma_r } も同様に定義します.

(2.7){displaystyle ;;; oldsymbol{v}_j = mathrm{arg  max}_{{ oldsymbol{v} perp oldsymbol{v}_1,ldots,oldsymbol{v}_{j-1},  ||oldsymbol{v}||=1 } } ||A oldsymbol{v}||, ;;;;;; j=2,ldots,r  }

(2.8){displaystyle ;;; sigma_j(A) = || A oldsymbol{v}_j || }

特異値の大小関係を明示しておきます.最後の {displaystyle gt 0 } は後述する(3.2)の直後の説明によります.

(2.9){displaystyle ;;; sigma_1(A) ge sigma_2(A) ge cdots ge sigma_r(A) gt 0 }


以下の定理は,上記の手順により導出される {displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r } が最良の部分空間を張ることを保証します.

定理 3.1
{displaystyle n 	imes d } 行列 {displaystyle A } とし,{displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r } は上記により定義される右特異ベクトルとする.{displaystyle 1 le k le r  } となる {displaystyle k } について,{displaystyle V_k }{displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_k } により張られる部分空間とする.このとき,各 {displaystyle k } について,{displaystyle V_k } は 点の集合 {displaystyle { oldsymbol{a}_i }_{i=1,ldots,n} } についての最良の {displaystyle k } 次元部分空間である.

証明:
{displaystyle k=1 } ならば明らかに成り立つ.

{displaystyle k=2 } のとき,平面 {displaystyle W } を点の集合 {displaystyle { oldsymbol{a}_i }_{i=1,ldots,n} } についての最良の {displaystyle 2 } 次元部分空間とする.{displaystyle W } の任意の基底 {displaystyle oldsymbol{w}_1,oldsymbol{w}_2 } について,{displaystyle  ||A oldsymbol{w}_1||^2 + || A oldsymbol{w}_2 ||^2 }{displaystyle { oldsymbol{a}_i }_{i=1,cdots,n} }{displaystyle W } への射影の長さの二乗の総和“の和”である.いま {displaystyle oldsymbol{w}_2 }{displaystyle oldsymbol{v}_1 } に直交するように基底 {displaystyle oldsymbol{w}_1,oldsymbol{w}_2 } をとることを考える.{displaystyle oldsymbol{v}_1 }{displaystyle W } に直交するならば,{displaystyle W } の要素となる任意の単位ベクトルは {displaystyle oldsymbol{w}_2 } となりうる.{displaystyle oldsymbol{v}_1 }{displaystyle W } に直交しないならば,{displaystyle oldsymbol{v}_1 }{displaystyle W } への射影に直交するように {displaystyle oldsymbol{w}_2 } をとる.{displaystyle oldsymbol{v} = oldsymbol{v}_1 }{displaystyle || A oldsymbol{v} ||^2 } を最大化するので,{displaystyle || A oldsymbol{w}_1 ||^2 le || A oldsymbol{v}_1 ||^2 } である.{displaystyle oldsymbol{v} = oldsymbol{v}_2 }{displaystyle oldsymbol{v}_1 } に直交するすべての {displaystyle oldsymbol{v} } のなかで {displaystyle || A oldsymbol{v} ||^2 } を最大化するので,{displaystyle || A oldsymbol{w}_2 ||^2 le || A oldsymbol{v}_2 ||^2 } である.したがって,

{displaystyle;;; || A oldsymbol{w}_1 ||^2 + || A oldsymbol{w}_2 ||^2 le || A oldsymbol{v}_1 ||^2 + || A oldsymbol{v}_2 ||^2 }

これより {displaystyle V_2 }{displaystyle W } よりも“より良い”最良の部分空間といえ,したがって {displaystyle V_2 } は最良の {displaystyle 2 } 次元空間であるといえる.

任意の {displaystyle k } のときを考える.{displaystyle V_{k-1} } が最良の {displaystyle k-1 } 次元部分空間であると仮定する. {displaystyle oldsymbol{w}_k }{displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_{k-1} } に直交するように基底 {displaystyle oldsymbol{w}_1, ldots ,oldsymbol{w}_k } をとると,仮定より

{displaystyle ;;; || A oldsymbol{w}_1 ||^2 + cdots + || A oldsymbol{w}_{k-1} ||^2 + || A oldsymbol{w}_k ||^2 le || A oldsymbol{v}_1 ||^2 + cdots + || A oldsymbol{v}_{k-1}||^2 + || A oldsymbol{w}_k ||^2 }

が成り立つ.{displaystyle oldsymbol{w}_k }{displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_{k-1} } に直交するので,{displaystyle  || A oldsymbol{w}_k ||^2 le || A oldsymbol{v}_k ||^2 } である.したがって

{displaystyle ;;; || A oldsymbol{w}_1 ||^2 + cdots + || A oldsymbol{w}_{k-1} ||^2 + || A oldsymbol{w}_k ||^2 le || A oldsymbol{v}_1 ||^2 + cdots + || A oldsymbol{v}_{k-1}||^2 + || A oldsymbol{v}_k ||^2 }

が成り立ち,{displaystyle V_k } は最良の {displaystyle k } 次元空間であることが示せた.(証明終わり)



[ 3. 右特異ベクトル再考 : 行空間との関係 ]
ここからは行空間 {displaystyle V } を導入し右特異ベクトルを別の視点で考えていきます.行列 {displaystyle A } の行(列)空間(row(column) space)とは,{displaystyle A } の行(列)ベクトルにより張られる空間のことです.行列の {displaystyle mathrm{rank} } は線形独立な行ベクトルの数に等しい(文献[3]にあります)ので {displaystyle mathrm{dim}V=mathrm{rank}A=r } です.(2.2)より {displaystyle oldsymbol{v} }{displaystyle mathrm{ker}A= { oldsymbol{v} in mathbb{R}^d ; A oldsymbol{v}= oldsymbol{0} }} の要素であることは,{displaystyle oldsymbol{v} }{displaystyle A } の(すべての)行ベクトル {displaystyle oldsymbol{a}_1,ldots,oldsymbol{a}_n } と 直交することと同値であることがわかります.すなわち {displaystyle oldsymbol{v} }{displaystyle mathrm{ker}A} の要素であることは,{displaystyle oldsymbol{v} } が行空間 {displaystyle V } のすべてのベクトルと直交することと同値であり,{displaystyle mathrm{ker}A }{displaystyle V } の直交補空間 {displaystyle V^{perp} } であることがわかります.以下の等式を得ます.{displaystyle oplus } は直交直和です.

(3.1){displaystyle ;;; V oplus V^{perp} = V oplus mathrm{ker} A = mathbb{R}^d }

階数・退化次数の定理(rank-nullity theorem)(文献[4]にあります)より以下が成り立ちます.

(3.2){displaystyle ;;; mathrm{dim}V + mathrm{dim}V^{perp} = mathrm{rank}A + mathrm{dim}(mathrm{ker}A) = r + mathrm{dim}(mathrm{ker}A) = d }

この等式から {displaystyle V } は右特異ベクトルの組 {displaystyle { oldsymbol{v}_1,ldots,oldsymbol{v}_r } } によって張られる空間になっていそうな雰囲気がしてきます.実際に {displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r 
otin mathrm{ker}A = V^{perp} } をみたす(すなわち {displaystyle ||Aoldsymbol{v}_j|| gt 0,  j=1,ldots,r} をみたす) {displaystyle V } の基底 {displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r } を(2.5)(2.7)により決めればよく,右特異ベクトルの組 {displaystyle { oldsymbol{v}_1,ldots,oldsymbol{v}_r } }{displaystyle A } の行空間 {displaystyle V } の正規直交基底であることがわかります.

まとめると,点の集合 {displaystyle { oldsymbol{a}_i }_{i=1,ldots,n} } の最良の {displaystyle r } 次元部分空間を張る右特異ベクトルの組 {displaystyle { oldsymbol{v}_1,ldots,oldsymbol{v}_r } }{displaystyle A } の行空間 {displaystyle V } の正規直交基底でもあります.各 {displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r } が張る空間をそれぞれ {displaystyle V_1,ldots,V_r } とすると(3.1)から以下を得ます.

(3.3){displaystyle ;;; V oplus V^{perp} = V oplus mathrm{ker} A }

{displaystyle ;;;;;;;;;;;;;;;;;;;;; = mathrm{span}{ oldsymbol{v}_1,ldots,oldsymbol{v}_r } oplus mathrm{ker} A }

{displaystyle ;;;;;;;;;;;;;;;;;;;;; = mathrm{span}{ oldsymbol{v}_1 } oplus cdots oplus mathrm{span}{ oldsymbol{v}_r } oplus mathrm{ker} A }

{displaystyle ;;;;;;;;;;;;;;;;;;;;; = V_1 oplus cdots oplus V_r oplus mathrm{ker} A }

{displaystyle ;;;;;;;;;;;;;;;;;;;;; = mathbb{R}^d }



[ 4. 特異値とフロベニウスノルムの関係式 ]

{displaystyle A } を以下のように展開することができます.3つめの等号では右特異ベクトルの組 {displaystyle { oldsymbol{v}_1,ldots,oldsymbol{v}_r } }{displaystyle A } の行空間 {displaystyle V } の正規直交基底であることを用いています.最後の等号は(2.2)を用いています.

(4.1){displaystyle ;;; A = egin{bmatrix} a_{11} & a_{12} & cdots & a_{1d}  a_{21} & a_{22} & cdots & a_{2d}  vdots & vdots & vdots & vdots  a_{n1} & a_{n2} & cdots & a_{nd} end{bmatrix}= egin{bmatrix} oldsymbol{a}_1^T  oldsymbol{a}_2^T  vdots  oldsymbol{a}_n^T end{bmatrix} = egin{bmatrix} langle oldsymbol{a}_1,oldsymbol{v}_1 
angle oldsymbol{v}_1^T + cdots + langle oldsymbol{a}_1,oldsymbol{v}_r 
angle oldsymbol{v}_r^T  langle oldsymbol{a}_2,oldsymbol{v}_1 
angle oldsymbol{v}_1^T + cdots + langle oldsymbol{a}_2,oldsymbol{v}_r 
angle oldsymbol{v}_r^T  vdots  langle oldsymbol{a}_n,oldsymbol{v}_1 
angle oldsymbol{v}_1^T + cdots + langle oldsymbol{a}_n,oldsymbol{v}_r 
angle oldsymbol{v}_r^T end{bmatrix} }

{displaystyle ;;;;;;;;;;;;; = egin{bmatrix} langle oldsymbol{a}_1,oldsymbol{v}_1 
angle   langle oldsymbol{a}_2,oldsymbol{v}_1 
angle  vdots  langle oldsymbol{a}_n,oldsymbol{v}_1 
angle end{bmatrix} oldsymbol{v}_1^T + cdots + egin{bmatrix} langle oldsymbol{a}_1,oldsymbol{v}_r 
angle   langle oldsymbol{a}_2,oldsymbol{v}_r 
angle  vdots  langle oldsymbol{a}_n,oldsymbol{v}_r 
angle end{bmatrix} oldsymbol{v}_r^T }

{displaystyle ;;;;;;;;;;;;; = (A oldsymbol{v}_1) oldsymbol{v}_1^T + cdots + (A oldsymbol{v}_r) oldsymbol{v}_r^T }

この展開式と {displaystyle ||oldsymbol{v}_1||=cdots=||oldsymbol{v}_r||=1 } より,行列 {displaystyle A } の大きさは {displaystyle  A oldsymbol{v}_1,ldots,A oldsymbol{v}_r } それぞれの大きさの総和に等しくなるような雰囲気がしてきます.実際に以下の補題が成り立ちます.

補題 3.2
任意の {displaystyle n 	imes d } 行列 {displaystyle A,  mathrm{rank}A = r } について,特異値の二乗の総和はフロベニウスノルム(文献[5]にあります)に等しい,すなわち以下が成り立つ.

{displaystyle ;;; sum_{i=1}^r sigma_i(A)^2 = || A  ||_F^2 ;;; left( =sum_{j,k} (a_{jk})^2 
ight)  }

証明:
{displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r }{displaystyle A } の行空間 {displaystyle V } を張る正規直交基底なので, {displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r } に直交するすべての {displaystyle oldsymbol{v} in mathbb{R}^n } について {displaystyle langle oldsymbol{a}_i , oldsymbol{v} 
angle =0 } であり,したがって

{displaystyle ;;; ||oldsymbol{a}_i||^2 = sum_{j=1}^r | langle oldsymbol{a}_i , oldsymbol{v}_j 
angle |^2, ;;; i=1,ldots,n }

が成り立つ.これを(4つめの等号に)用いると

{displaystyle ; sum_{j=1}^r sigma_j(A)^2  = sum_{j=1}^r  || A oldsymbol{v}_j ||^2 = sum_{j=1}^r sum_{i=1}^n  | langle oldsymbol{a}_i , oldsymbol{v}_j 
angle |^2 = sum_{i=1}^n sum_{j=1}^r | langle oldsymbol{a}_i , oldsymbol{v}_j 
angle |^2 = sum_{i=1}^n ||oldsymbol{a}_i||^2 = sum_{i=1}^n sum_{k=1}^d |a_{ik}|^2  }

{displaystyle ;;;;;;;;;;;;;;;;; = || A  ||_F^2  }

となり補題は示せた.(証明終わり)



[ 5. 左特異ベクトル ]
(3.3)より,あらゆる {displaystyle oldsymbol{v} in mathbb{R}^d }{displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r } あるいは(すべての) {displaystyle oldsymbol{v}_1,ldots,oldsymbol{v}_r } に直交するベクトルの線形結合により表現可能です.したがって(2.2)(3.3)よりあらゆる {displaystyle A oldsymbol{v} }{displaystyle A oldsymbol{v}_1,ldots,A oldsymbol{v}_r } の線形結合により表現可能です.これらのベクトルを正規化した以下を左特異ベクトルといいます.

(5.1){displaystyle ;;; oldsymbol{u}_i=  frac{1}{|| A oldsymbol{v}_i ||} A oldsymbol{v}_i = frac{1}{sigma_i(A)} A oldsymbol{v}_i, ;;; i = 1 ,ldots, r }

以下の定理が成り立ちます.

定理 3.7
左特異ベクトル {displaystyle oldsymbol{u}_1,ldots,oldsymbol{u}_r } はそれぞれ直交する.

証明:
省略.文献[1]Theorem 3.7 参照.



[ 6. 特異値分解 ]
本章では {displaystyle sigma_i(A) }{displaystyle sigma_i } とします.
以下を定義します.

(6.1){displaystyle ;;; U = egin{bmatrix} oldsymbol{u}_1 & oldsymbol{u}_2 & cdots & oldsymbol{u}_r end{bmatrix} = egin{bmatrix} u_{11} & u_{21} & cdots & u_{r1}  u_{12} & u_{22} & cdots & u_{r2}  vdots & vdots & vdots & vdots  u_{1n} & u_{2n} & cdots & u_{rn} end{bmatrix} }

(6.2){displaystyle ;;; D = egin{bmatrix} sigma_{1} & 0 & cdots & 0  0 & sigma_{2} & cdots & 0  vdots & vdots & ddots & vdots  0 & 0 & cdots & sigma_{r} end{bmatrix} }

(6.3){displaystyle ;;; V = egin{bmatrix} oldsymbol{v}_1 & oldsymbol{v}_2 & cdots & oldsymbol{v}_r end{bmatrix} = egin{bmatrix} v_{11} & v_{21} & cdots & v_{r1}  v_{12} & v_{22} & cdots & v_{r2}  vdots & vdots & vdots & vdots  v_{1d} & v_{2d} & cdots & v_{rd} end{bmatrix} }


特異値分解は以下の式変形から得ることができます.途中まで(4.1)と同じです.

(6.4){displaystyle ;;; A = egin{bmatrix} a_{11} & a_{12} & cdots & a_{1d}  a_{21} & a_{22} & cdots & a_{2d}  vdots & vdots & vdots & vdots  a_{n1} & a_{n2} & cdots & a_{nd} end{bmatrix}= egin{bmatrix} oldsymbol{a}_1^T  oldsymbol{a}_2^T  vdots  oldsymbol{a}_n^T end{bmatrix} = egin{bmatrix} langle oldsymbol{a}_1,oldsymbol{v}_1 
angle oldsymbol{v}_1^T + cdots + langle oldsymbol{a}_1,oldsymbol{v}_r 
angle oldsymbol{v}_r^T  langle oldsymbol{a}_2,oldsymbol{v}_1 
angle oldsymbol{v}_1^T + cdots + langle oldsymbol{a}_2,oldsymbol{v}_r 
angle oldsymbol{v}_r^T  vdots  langle oldsymbol{a}_n,oldsymbol{v}_1 
angle oldsymbol{v}_1^T + cdots + langle oldsymbol{a}_n,oldsymbol{v}_r 
angle oldsymbol{v}_r^T end{bmatrix} }

{displaystyle ;;;;;;;;;;;;; = egin{bmatrix} langle oldsymbol{a}_1,oldsymbol{v}_1 
angle   langle oldsymbol{a}_2,oldsymbol{v}_1 
angle  vdots  langle oldsymbol{a}_n,oldsymbol{v}_1 
angle end{bmatrix} oldsymbol{v}_1^T + cdots + egin{bmatrix} langle oldsymbol{a}_1,oldsymbol{v}_r 
angle   langle oldsymbol{a}_2,oldsymbol{v}_r 
angle  vdots  langle oldsymbol{a}_n,oldsymbol{v}_r 
angle end{bmatrix} oldsymbol{v}_r^T }

{displaystyle ;;;;;;;;;;;;; = (A oldsymbol{v}_1) oldsymbol{v}_1^T + cdots + (A oldsymbol{v}_r) oldsymbol{v}_r^T }

{displaystyle ;;;;;;;;;;;;; = || A oldsymbol{v}_1 || left(frac{1}{|| A oldsymbol{v}_1 ||} A oldsymbol{v}_1 
ight) oldsymbol{v}_1^T + cdots + || A oldsymbol{v}_r || left( frac{1}{|| A oldsymbol{v}_r ||} A oldsymbol{v}_r 
ight) oldsymbol{v}_r^T }

{displaystyle ;;;;;;;;;;;;; = sigma_1 oldsymbol{u}_1 oldsymbol{v}_1^T + cdots + sigma_r oldsymbol{u}_r oldsymbol{v}_r^T }

{displaystyle ;;;;;;;;;;;;; = sum_{i=1}^r sigma_i oldsymbol{u}_i oldsymbol{v}_i^T }

{displaystyle ;;;;;;;;;;;;; = sum_{i=1}^r sigma_i egin{bmatrix} u_{i1}  u_{i2}  vdots  vdots  u_{in} end{bmatrix} egin{bmatrix} v_{i1} & v_{i2} & cdots & v_{id} end{bmatrix} }

{displaystyle ;;;;;;;;;;;;; = sum_{i=1}^r egin{bmatrix} sigma_i u_{i1} v_{i1}  & sigma_i u_{i1} v_{i2} & cdots & sigma_i u_{i1} v_{id}  sigma_i u_{i2} v_{i1} & sigma_i u_{i2} v_{i2} & cdots & sigma_i u_{i2} v_{id}  vdots & vdots & ddots & vdots  vdots & vdots & ddots & vdots  sigma_i u_{in} v_{i1} & sigma_i u_{in} v_{i2} & cdots & sigma_i u_{in} v_{id} end{bmatrix} }

{displaystyle ;;;;;;;;;;;;; = egin{bmatrix} u_{11} & u_{21} & cdots & u_{r1}  u_{12} & u_{22} & cdots & u_{r2}  vdots & vdots & vdots & vdots  vdots & vdots & vdots & vdots  u_{1n} & u_{2n} & cdots & u_{rn} end{bmatrix} egin{bmatrix} sigma_1 v_{11} & sigma_1 v_{12} & cdots & sigma_1 v_{1d}  sigma_2 v_{21} & sigma_2 v_{22} & cdots & sigma_2 v_{2d}  vdots & vdots & ddots & vdots  sigma_r v_{r1} & sigma_r v_{r2} & cdots & sigma_r v_{rd} end{bmatrix} }

{displaystyle ;;;;;;;;;;;;; = egin{bmatrix} u_{11} & u_{21} & cdots & u_{r1}  u_{12} & u_{22} & cdots & u_{r2}  vdots & vdots & vdots & vdots  vdots & vdots & vdots & vdots  u_{1n} & u_{2n} & cdots & u_{rn} end{bmatrix} egin{bmatrix} sigma_{1} & 0 & cdots & 0  0 & sigma_{2} & cdots & 0  vdots & vdots & vdots & vdots   0 & 0 & cdots & sigma_{r} end{bmatrix} egin{bmatrix} v_{11} & v_{12} & cdots & cdots & v_{1d}  v_{21} & v_{22} & cdots & cdots & v_{2d}  vdots & vdots & vdots & vdots & vdots  v_{r1} & v_{r2} & cdots & cdots & v_{rd} end{bmatrix} }

{displaystyle ;;;;;;;;;;;;; = egin{bmatrix} oldsymbol{u}_1 & oldsymbol{u}_2 & cdots & oldsymbol{u}_r end{bmatrix} D egin{bmatrix} oldsymbol{v}_1^T  oldsymbol{v}_2^T  vdots  oldsymbol{v}_r^T end{bmatrix}  }

{displaystyle ;;;;;;;;;;;;; = U D V^T  }



[ 7. 左特異ベクトル再考 : 列空間との関係 ]
ここまで行列 {displaystyle A } について行ってきた議論を行列 {displaystyle A^T } について行うことを考えます.よく知られている性質(文献[3]にあります)を用いると {displaystyle mathrm{rank}A^T=mathrm{rank}A=r } であるから全く同じ議論が可能です.ただし右特異ベクトルの記号に ( {displaystyle d 	imes 1 } 単位ベクトル {displaystyle oldsymbol{v}_j'} ではなく) {displaystyle n 	imes 1 } 単位ベクトル {displaystyle oldsymbol{u}_j' } を用います.すると {displaystyle { oldsymbol{u}_1',ldots, oldsymbol{u}_r' } } は行列 {displaystyle A^T } の行空間の正規直交基底であるので行列 {displaystyle A } の列空間の正規直交基底でもあります.補題 3.2を用いると

(7.1){displaystyle ;;; sum_{i=1}^r sigma_i(A)^2 = || A  ||_F^2 = || A^T ||_F^2 = sum_{i=1}^r sigma_i(A^T)^2 }

なので,{displaystyle A }{displaystyle A^T } の特異値は等しいことの必要条件を得ます.一方,(6.4)より

(7.2){displaystyle ;;;;;;;;;;;;; A^T = (V^T)^T (UD)^T = V D U^T  }

であり,これは 行列 {displaystyle A^T } の特異値分解とみなせるので,(5.1)による {displaystyle { oldsymbol{u}_1,ldots, oldsymbol{u}_r } } は行列 {displaystyle A } の列空間の正規直交基底であることがわかります.

=================================================================================

以上,特異値分解の導出と左特異ベクトル,特異値,右特異ベクトルとは何かについて考えてみました.



参考文献
[1] Carnegie Mellon University Avrim Blum先生らによるノート http://www.cs.cornell.edu/jeh/book.pdf
[2] Wikipedia Kernel (linear algebra)のページ https://en.wikipedia.org/wiki/Kernel_(linear_algebra)
[3] Wikipedia Rank (linear algebra)のページ https://en.wikipedia.org/wiki/Rank_(linear_algebra)
[4] Wikipedia Rank-nullity theoremのページ https://en.wikipedia.org/wiki/Rank%E2%80%93nullity_theorem
[5] Wikipedia Matrix norm のページ https://en.wikipedia.org/wiki/Matrix_norm
[6] Massachusetts Institute of Technology Gilbert Strang先生のノート https://ocw.mit.edu/courses/mathematics/18-06sc-linear-algebra-fall-2011/positive-definite-matrices-and-applications/singular-value-decomposition/MIT18_06SCF11_Ses3.5sum.pdf
[7] 京都大学 大和田拓先生のノート http://fd.kuaero.kyoto-u.ac.jp/sites/default/files/linear_algebra.pdf