応用上よく使われる特異値分解(singular value decomposition ; SVD)について,どのように導出するのか,左特異ベクトル,特異値,右特異ベクトルがいったい何なのかという点にいつもモヤモヤしてしまうので,その内容を調べてまとめることにしました.
文献[1]の3章をベースにしてまとめますが,行間を埋めるための説明や式変形の途中経過を追加しています.また定理の証明を省略している箇所があります.
=================================================================================
特異値分解は複素数を要素にもつ行列に対する概念ですが,本記事で扱う行列,ベクトルの要素はすべて実数であるとします.
[ 1. 最良の部分空間 ]
の 実行列 の行ベクトルを 次元空間における 個の点と解釈し,それらの点の集合についての最良の 次元部分空間を見つけることを考えます.“最良”とは, 個の各点から部分空間へ(直交する方向)の距離の二乗の総和が最小となることを意味します.
簡単化のため,部分空間が 次元空間,すなわち原点を通る直線の場合を考えます.空間上の点の集合 に対して最もあてはまりのよい原点を通る直線を探すことは,点から直線へ(直交する方向)の距離の二乗の総和を最小化すること,すなわち最良の 次元部分空間を見つけることを意味します. から原点を通る直線へ射影することを考えると,三平方の定理より以下が成り立ちます.
(1.1)
したがってすべての点について考えると以下が成り立ちます.
(1.2)
最良の 次元部分空間を見つけるためには,右辺第一項は定数なので の総和を最小化する,すなわち の総和を最大化すればよいことがわかります.
同様に,最良の 次元部分空間を見つけるためにはその部分空間への射影を考え, の総和を最大化すればよいことになります.ここまでで,最良の 次元部分空間の意味とその導出のための手がかりが明らかになりました.次の章ではその部分空間の基底を導出していきます.
[ 2. 右特異ベクトルと特異値の導出 ]
実行列 の要素からなる ベクトル を
(2.1)
のように定義し, 次元空間における 個の点とみなします.その 次元空間の原点を通るある直線上の 単位ベクトルを とします. は通常の内積, はユークリッドノルムです.以下を得ることができます. は の への射影の長さを意味します.
(2.2)
(2.3)
(2.4)
(2.4)はまさに(1.2)の右辺第二項(の符号反転),すなわち の総和に相当します.これを用いて行列 の第1右特異ベクトル ,第1特異値 を定義します. は点の集合 の最良の 次元部分空間, は への射影の長さの二乗の総和です.
(2.5)
(2.6)
次に を基底(の1つ)とする最良の 次元部分空間を見つけることを考えます.三平方の定理より,その 次元部分空間への射影の長さの二乗の総和は, への射影の長さの二乗の総和と に直交するベクトルへの射影の長さの二乗の総和“の和”に等しくなります.したがって, を基底(の1つ)とする最良の 次元部分空間を見つけるためには,射影の長さ を最大にする単位ベクトル を見つければよいことになります.第2特異ベクトル ,第2特異値 を定義します.以降の右特異ベクトル と特異値 も同様に定義します.
(2.7)
(2.8)
特異値の大小関係を明示しておきます.最後の は後述する(3.2)の直後の説明によります.
(2.9)
以下の定理は,上記の手順により導出される が最良の部分空間を張ることを保証します.
定理 3.1
行列 とし, は上記により定義される右特異ベクトルとする. となる について, を により張られる部分空間とする.このとき,各 について, は 点の集合 についての最良の 次元部分空間である.
証明:
ならば明らかに成り立つ.
のとき,平面 を点の集合 についての最良の 次元部分空間とする. の任意の基底 について, は の への射影の長さの二乗の総和“の和”である.いま が に直交するように基底 をとることを考える. が に直交するならば, の要素となる任意の単位ベクトルは となりうる. が に直交しないならば, の への射影に直交するように をとる. は を最大化するので, である. は に直交するすべての のなかで を最大化するので, である.したがって,
これより は よりも“より良い”最良の部分空間といえ,したがって は最良の 次元空間であるといえる.
任意の のときを考える. が最良の 次元部分空間であると仮定する. が に直交するように基底 をとると,仮定より
が成り立つ. が に直交するので, である.したがって
が成り立ち, は最良の 次元空間であることが示せた.(証明終わり)
[ 3. 右特異ベクトル再考 : 行空間との関係 ]
ここからは行空間 を導入し右特異ベクトルを別の視点で考えていきます.行列 の行(列)空間(row(column) space)とは, の行(列)ベクトルにより張られる空間のことです.行列の は線形独立な行ベクトルの数に等しい(文献[3]にあります)ので です.(2.2)より が の要素であることは, が の(すべての)行ベクトル と 直交することと同値であることがわかります.すなわち が の要素であることは, が行空間 のすべてのベクトルと直交することと同値であり, は の直交補空間 であることがわかります.以下の等式を得ます. は直交直和です.
(3.1)
階数・退化次数の定理(rank-nullity theorem)(文献[4]にあります)より以下が成り立ちます.
(3.2)
この等式から は右特異ベクトルの組 によって張られる空間になっていそうな雰囲気がしてきます.実際に をみたす(すなわち をみたす) の基底 を(2.5)(2.7)により決めればよく,右特異ベクトルの組 は の行空間 の正規直交基底であることがわかります.
まとめると,点の集合 の最良の 次元部分空間を張る右特異ベクトルの組 は の行空間 の正規直交基底でもあります.各 が張る空間をそれぞれ とすると(3.1)から以下を得ます.
(3.3)
[ 4. 特異値とフロベニウスノルムの関係式 ]
を以下のように展開することができます.3つめの等号では右特異ベクトルの組 が の行空間 の正規直交基底であることを用いています.最後の等号は(2.2)を用いています.
(4.1)
この展開式と より,行列 の大きさは それぞれの大きさの総和に等しくなるような雰囲気がしてきます.実際に以下の補題が成り立ちます.
補題 3.2
任意の 行列 について,特異値の二乗の総和はフロベニウスノルム(文献[5]にあります)の二乗に等しい,すなわち以下が成り立つ.
証明:
は の行空間 を張る正規直交基底なので, に直交するすべての について であり,したがって
が成り立つ.これを(4つめの等号に)用いると
となり補題は示せた.(証明終わり)
[ 5. 左特異ベクトル ]
(3.3)より,あらゆる は あるいは(すべての) に直交するベクトルの線形結合により表現可能です.したがって(2.2)(3.3)よりあらゆる は の線形結合により表現可能です.これらのベクトルを正規化した以下を左特異ベクトルといいます.
(5.1)
以下の定理が成り立ちます.
定理 3.7
左特異ベクトル はそれぞれ直交する.
証明:
省略.文献[1]Theorem 3.7 参照.
[ 6. 特異値分解 ]
本章では を とします.
以下を定義します.
(6.1)
(6.2)
(6.3)
特異値分解は以下の式変形から得ることができます.途中まで(4.1)と同じです.
(6.4)
[ 7. 左特異ベクトル再考 : 列空間との関係 ]
ここまで行列 について行ってきた議論を行列 について行うことを考えます.よく知られている性質(文献[3]にあります)を用いると であるから全く同じ議論が可能です.ただし右特異ベクトルの記号に ( 単位ベクトル ではなく) 単位ベクトル を用います.すると は行列 の行空間の正規直交基底であるので行列 の列空間の正規直交基底でもあります.補題 3.2を用いると
(7.1)
なので, と の特異値は等しいことの必要条件を得ます.一方,(6.4)より
(7.2)
であり,これは 行列 の特異値分解とみなせるので,(5.1)による は行列 の列空間の正規直交基底であることがわかります.
=================================================================================
以上,特異値分解の導出と左特異ベクトル,特異値,右特異ベクトルとは何かについて考えてみました.
参考文献
[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