特異値分解とくいちぶんかいsingular value decompositionSVDの入口いりぐち

1導入どうにゅう

この講義こうぎで重要じゅうようなのは、特異値分解とくいちぶんかいsingular value decompositionSVDは、正方行列せいほうぎょうれつsquare matrixに限定げんていされない行列ぎょうれつmatrixを、直交変換ちょっこうへんかんと軸方向じくほうこうの伸縮しんしゅくへ分解ぶんかいする方法ほうほうであるということである。

固有値こゆうちeigenvalueと対角化たいかくかdiagonalizationは正方行列せいほうぎょうれつsquare matrixを主対象しゅたいしょうにする。一方いっぽう、実務じつむや応用おうようでは、縦横たてよこの大おおきさが異ことなる行列ぎょうれつmatrixが頻出ひんしゅつする。特異値分解とくいちぶんかいsingular value decompositionSVDは、そのような長方行列ちょうほうぎょうれつにも適用てきようできる標準的ひょうじゅんてきな分解ぶんかいである。

SVD は、一般いっぱんの行列ぎょうれつmatrixに対たいする「直交基底ちょっこうきていつきの最もっとも安定あんていした分解ぶんかい」と位置付いちづけられる。入力側にゅうりょくがわの正規直交基底せいきちょっこうきていorthonormal basis、出力側しゅつりょくがわの正規直交基底せいきちょっこうきていorthonormal basis、軸方向じくほうこうの非負ひふの伸縮率しんしゅくりつを分離ぶんりするため、階数かいすうrank、最小二乗法さいしょうにじょうほうleast squares method、擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrix、低階数近似ていかいすうきんじを同一どういつの枠組わくぐみで記述きじゅつできる。

2用語ようごと定義ていぎ

特異値分解とくいちぶんかいSingular value decomposition とは、実じつrealの $$m\times n$$m\times n 行列ぎょうれつmatrix $$A$$A を

と表示ひょうじすることである。ここで $$U$$U は $$m\times m$$m\times m 直交行列ちょっこうぎょうれつorthogonal matrix、$$V$$V は $$n\times n$$n\times n 直交行列ちょっこうぎょうれつorthogonal matrix、$$\mathrm{\Sigma }$$\Sigma は対角方向たいかくほうこうに非負数ひふすうを並ならべた $$m\times n$$m\times n 行列ぎょうれつmatrixである。

$$\mathrm{\Sigma }$$\Sigma の対角成分たいかくせいぶん

を $$A$$A の特異値とくいちSingular valuesという。複素行列ふくそぎょうれつでは

と表示ひょうじする。

3方針ほうしん

方針ほうしんは、実行列じつぎょうれつでは $$A^{T}A$$A^TA、複素行列ふくそぎょうれつでは $$A^{*}A$$A^*A を解析かいせきすることである。$$A^{T}A$$A^TA は実対称じつたいしょうかつ非負定値ひふていちであり、$$A^{*}A$$A^*A はエルミート行列ぎょうれつmatrixかつ非負定値ひふていちであるため、直交ちょっこうorthogonalまたはユニタリに対角化たいかくかdiagonalizationできる。

なぜ $$A^{*}A$$A^*A を見みるかというと、任意にんいの $$x$$x に対たいして

となるからである。したがって $$A^{*}A$$A^*A はエルミート行列ぎょうれつHermitian matrixかつ非負定値ひふていちであり、固有値こゆうちeigenvalueは 0 以上いじょうの実数じっすうreal numberになる。この固有値こゆうちeigenvalueの平方根へいほうこんが特異値とくいちsingular valueである。

複素ふくそcomplexの場合ばあいは

である。この固有値こゆうちeigenvalue $${\lambda }_i$$\lambda_i は非負ひふであり、$${\sigma }_i=\sqrt{{\lambda }_i}$$\sigma_i=\sqrt{\lambda_i} が特異値とくいちsingular valueになる。

4直感的ちょっかんてきな説明せつめい

特異値分解とくいちぶんかいsingular value decompositionSVDは、行列ぎょうれつmatrix $$A$$A の作用さようを

に分解ぶんかいする。直交変換ちょっこうへんかんは長ながさと角度かくどを保存ほぞんし、$$\mathrm{\Sigma }$$\Sigma だけが長ながさを変更へんこうする。したがって特異値とくいちsingular valueは、行列ぎょうれつmatrixが各主方向かくしゅほうこうをどれだけ伸縮しんしゅくするかを表あらわす。

5厳密げんみつな説明せつめい

5.11. $$A^{T}A$$A^TA または $$A^{*}A$$A^*A から右特異みぎとくいベクトルを得える

実行列じつぎょうれつでは $$A^{T}A$$A^TA が実対称行列じつたいしょうぎょうれつである。したがって正規直交せいきちょっこう固有ベクトルeigenvector $$v_1,\text{[PARSE ERROR: Undefined("Command("dots")")]},v_n$$v_1,\dots,v_n を選択せんたくできる。

である。この $$v_i$$v_i が右特異みぎとくいベクトルである。複素行列ふくそぎょうれつでは $$A^{*}A$$A^*A を用もちい、

と記述きじゅつする。この変更へんこうにより、定義ていぎの $$A=U\mathrm{\Sigma }{V}^{*}$$A=U\Sigma V^* と導出どうしゅつの記法きほうが整合せいごうする。

5.22. 左特異ひだりとくいベクトルを構成こうせいする

$${\sigma }_i>0$$\sigma_i>0 のとき

と定義ていぎする。この $$u_i$$u_i は互たがいに直交ちょっこうorthogonalし、長ながさ 1 である。これを補完ほかんして $$R^m$$\mathbb R^m の正規直交基底せいきちょっこうきていorthonormal basisにすると、$$U$$U が得えられる。

左特異ひだりとくいベクトルは $$A{A}^T$$AA^T からも特徴付とくちょうづけられる。実行列じつぎょうれつでは

であり、複素ふくそcomplex行列ぎょうれつmatrixでは

である。つまり、$$A^{T}A$$A^TA または $$A^{*}A$$A^*A は入力側にゅうりょくがわの主方向しゅほうこうを与あたえ、$$A{A}^T$$AA^T または $$A{A}^{*}$$AA^* は出力側しゅつりょくがわの主方向しゅほうこうを与あたえる。

5.33. 階数かいすうrankとの関係かんけい

非零特異値ひぜろとくいちの個数こすうは $$A$$A の階数かいすうrankに等ひとしい。

小ちいさい特異値とくいちsingular valueは、行列ぎょうれつmatrixが情報じょうほうを強つよく圧縮あっしゅくする方向ほうこうを示しめす。

5.44. コンパクト SVD と基本部分空間きほんぶぶんくうかん

$$A$$A の階数かいすうrankを $$r$$r とし、正せいの特異値とくいちsingular valueだけを残のこすと

と表示ひょうじできる。これをコンパクト SVDCompact SVDという。複素ふくそcomplexの場合ばあいは $$V_{r^{*}}$$V_r^* を用もちいる。

この表示ひょうじでは、$$U_r$$U_r の列れつcolumnが $$\mathrm{Col}\left(A\right)$$\operatorname{Col}(A) の正規直交基底せいきちょっこうきていorthonormal basisを与あたえ、$$V_r$$V_r の列れつcolumnが $$\mathrm{Row}\left(A\right)$$\operatorname{Row}(A) の正規直交基底せいきちょっこうきていorthonormal basisを与あたえる。さらに、零特異値ぜろとくいちに対応たいおうする右特異みぎとくいベクトルは $$\ker \left(A\right)$$\ker(A) を、零特異値ぜろとくいちに対応たいおうする左特異ひだりとくいベクトルは $$\ker \left(A^T\right)$$\ker(A^T) または $$\ker \left(A^{*}\right)$$\ker(A^*) を記述きじゅつする。

5.55. 低階数近似ていかいすうきんじへの接続せつぞく

特異値とくいちsingular valueを大おおきい順じゅんに並ならべ、上位じょうい $$k$$k 個こだけを残のこすと

を得える。複素ふくそcomplexの場合ばあいは $$v_{i^{*}}$$v_i^* を用もちいる。Eckart-Young の定理ていりにより、$$A_k$$A_k は階数かいすうrank $$k$$k 以下いかの行列ぎょうれつmatrixの中なかで $$A$$A に最もっとも近ちかい近似きんじを与あたえる。

である。この事実じじつにより、SVD は分解ぶんかいの存在そんざいだけでなく、圧縮あっしゅくや雑音除去ざつおんじょきょの基礎きそにもなる。

6具体例ぐたいていれい

では、すでに軸方向じくほうこうの伸縮しんしゅくが分離ぶんりされている。したがって

とでき、特異値とくいちsingular valueは $$3,1$$3,1 である。

一般いっぱんの行列ぎょうれつmatrixでは、まず $$V^T$$V^T が入力空間にゅうりょくくうかんinput spaceを主方向しゅほうこうへ回転かいてんし、$$\mathrm{\Sigma }$$\Sigma が伸縮しんしゅくし、$$U$$U が出力空間しゅつりょくくうかんへ配置はいちする。

非対角ひたいかくな例れいとして、

を考かんがえる。このとき

であり、その固有値こゆうちeigenvalueは

である。したがって特異値とくいちsingular valueは

となる。$$A$$A 自身じしんの固有値こゆうちeigenvalueは $$1$$1 だけであるが、特異値とくいちsingular valueは $$A$$A が長ながさをどれだけ伸のばすかを記録きろくする。SVD は固有値こゆうちeigenvalueの代替だいたいではなく、別べつの、より幾何的きかてきで安定あんていした量りょうquantityを測はかる。

7別べつの観点かんてん

特異値分解とくいちぶんかいsingular value decompositionSVDは、最小二乗法さいしょうにじょうほうleast squares methodと擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixの基礎きそである。$$A$$A が正則せいそくでなくても、非零特異値ひぜろとくいちの方向ほうこうだけを反転はんてんすることで、最小さいしょうノルム解かいを定義ていぎできる。

8判定基準はんていきじゅん

• 特異値とくいちsingular valueは $$A^{T}A$$A^TA の固有値こゆうちeigenvalueの平方根へいほうこんである。
• 非零特異値ひぜろとくいちの個数こすうは階数かいすうrankである。
• 特異値分解とくいちぶんかいsingular value decompositionSVDは長方行列ちょうほうぎょうれつにも適用てきようできる。
• 小ちいさい特異値とくいちsingular valueは情報じょうほうの圧縮あっしゅくや数値的不安定性すうちてきふあんていせいと関係かんけいする。
• コンパクト SVD は、列空間れつくうかんcolumn space・行空間ぎょうくうかんrow space・核かくkernelを同時どうじに記述きじゅつする。

9どこまで成立せいりつするか

特異値分解とくいちぶんかいsingular value decompositionSVDは任意にんいの実行列じつぎょうれつ・複素行列ふくそぎょうれつに成立せいりつする。固有値分解こゆうちぶんかいとは異ことなり、正方行列せいほうぎょうれつsquare matrixや対角化可能性たいかくかかのうせいを前提ぜんていにしない。

10存在定理そんざいていりと証明しょうめいの骨格こっかく

任意にんいの $$m\times n$$m\times n 実行列じつぎょうれつ $$A$$A について、直交行列ちょっこうぎょうれつorthogonal matrix $$U,V$$U,V と非負ひふの対角成分たいかくせいぶんをもつ $$m\times n$$m\times n 行列ぎょうれつ $$\mathrm{\Sigma }$$\Sigma が存在そんざいして

と書かける。複素行列ふくそぎょうれつcomplex matrixでは

である。

証明しょうめいの骨格こっかくは $$A^{T}A$$A^TA または $$A^{*}A$$A^*A のスペクトル定理ていりspectral theoremである。$$A^{*}A$$A^*A はエルミート行列ぎょうれつHermitian matrixであり、

なので非負定値ひふていちである。したがって正規直交せいきちょっこう固有ベクトルeigenvector $$v_i$$v_i と非負ひふの固有値こゆうちeigenvalue $${\lambda }_i$$\lambda_i を持もつ。$${\sigma }_i=\sqrt{{\lambda }_i}$$\sigma_i=\sqrt{\lambda_i} と置おき、$${\sigma }_i>0$$\sigma_i>0 について

と定義ていぎする。すると

より $$u_i$$u_i は互たがいに直交ちょっこうorthogonalし、長ながさ 1 になる。残のこりの $$u_i$$u_i を補完ほかんすれば $$U$$U が得えられる。この構成こうせいが SVD の存在そんざいを説明せつめいする。

11基本部分空間きほんぶぶんくうかんの対応たいおう

SVD は、4 つの基本部分空間きほんぶぶんくうかんを同時どうじに整理せいりする。

このため SVD は、階数かいすうrankだけでなく、解かいが失うしなわれる方向ほうこう、列空間れつくうかんへの射影しゃえいprojection、最小二乗解さいしょうにじょうかいを同時どうじに記述きじゅつできる。

12別べつの見方みかた

SVD は、最小二乗法さいしょうにじょうほうleast squares methodと擬似逆行列ぎじぎゃくぎょうれつpseudoinverse matrixの基礎きそでもある。$$A$$A が可逆かぎゃくinvertibleでなくても、正せいの特異値とくいちsingular valueをもつ特異方向とくいほうこうsingular directionは逆向ぎゃくむきに戻もどせる一方いっぽう、$${\sigma }_i=0$$\sigma_i=0 の方向ほうこうは失うしなわれた情報じょうほうとして扱あつかう。

13計算例けいさんれい：非対角ひたいかくな $$2\times 2$$2\times2 行列ぎょうれつ

を考かんがえる。このとき

であり、固有値こゆうちeigenvalueは

である。したがって特異値とくいちsingular valueは

である。ここで $$A$$A 自身じしんの固有値こゆうちeigenvalueは $$1$$1 の重複ちょうふくであるが、特異値とくいちsingular valueは $$A^{T}A$$A^TA の平方根へいほうこんとして別べつの量りょうを測はかっている。つまり SVD は「固有値こゆうちeigenvalueの代替だいたい」ではなく、入力方向にゅうりょくほうこうの長ながさがどれだけ伸のびるかを測はかる分解ぶんかいである。

14判定基準はんていきじゅん

• 特異値とくいちsingular valueは $$A^{T}A$$A^TA または $$A^{*}A$$A^*A の固有値こゆうちeigenvalueの平方根へいほうこんである。
• 正せいの特異値とくいちsingular valueの個数こすうが階数かいすうrankである。
• SVD は長方行列ちょうほうぎょうれつにも適用てきようできる。
• 小ちいさい特異値とくいちsingular valueは、圧縮あっしゅくや数値的すうちてきな不安定性ふあんていせいを示しめすことがある。
• コンパクト SVD は、列空間れつくうかんcolumn space、行空間ぎょうくうかんrow space、核かくを同時どうじに記述きじゅつする。

15低階数近似ていかいすうきんじの意味いみと注意ちゅうい

Eckart-Young の定理ていりは、上位じょうい $$k$$k 個この特異値とくいちsingular valueだけを残のこした

が、階数かいすう $$k$$k 以下いかの行列ぎょうれつmatrixの中なかで $$A$$A に最もっとも近ちかいことを主張しゅちょうする。ただし、小ちいさい特異値とくいちsingular valueを切きることは情報じょうほうを捨すてることでもある。ノイズ除去じょきょや圧縮あっしゅくでは有効ゆうこうだが、小ちいさい特異値とくいちsingular valueの方向ほうこうが意味いみのある信号しんごうを含ふくむ場合ばあいには注意ちゅういが必要ひつようである。

16適用範囲てきようはんいと限界げんかい

SVD は、実じつまたは複素ふくそのすべての行列ぎょうれつmatrixに存在そんざいする。固有値分解こゆうちぶんかいeigenvalue decompositionと違ちがい、正方せいほうであることや対角化可能たいかくかかのうdiagonalizableであることを仮定かていしない。ただし、特異値とくいちsingular valueだけでは符号ふごう、位相いそう、固有こゆうベクトルeigenvectorの振ふる舞まいは捉とらえられない。特異値とくいちsingular valueが記述きじゅつするのは長ながさの伸のびである。

17最終形さいしゅうけい

18一言ひとことでいうと

• 特異値分解とくいちぶんかいsingular value decompositionSVDは、任意にんいの行列ぎょうれつmatrixを直交変換ちょっこうへんかんと軸方向じくほうこうの伸縮しんしゅくへ分解ぶんかいする標準形ひょうじゅんけいである。

19演習えんしゅうリンク

20関連かんれんリンク