奇き异值分解ぶんかい

奇き异值分解ぶんかい（英語えいご：Singular value decomposition，縮寫しゅくしゃ：SVD）是これ线性代数だいすう中ちゅう一いち种重要じゅうよう的てき矩のり阵分解ぶんかい，在ざい信号しんごう处理、统计学がく等とう领域有ゆう重要じゅうよう应用。奇き异值分解ぶんかい在ざい某ぼう些方面めん与あずか对称矩のり阵或ある厄やく米まい矩のり陣じん基もと于特とく征せい向こう量りょう的てき对角化か类似。然しか而这两种矩のり阵分解ぶんかい尽つき管かん有ゆう其相关性，但ただし还是有明ありあけ显的不同ふどう。对称阵特征せい向こう量りょう分解ぶんかい的てき基もと础是谱分析ぶんせき，而奇异值分解ぶんかい则是谱分析理论在任意にんい矩のり阵上的てき推广。

理論りろん描述

假設かせつM是ぜ一いち個こm×n階かい矩のり陣じん，其中的てき元素げんそ全部ぜんぶ屬ぞく於域いきK，也就是ぜ實數じっすう域いき或ある複數ふくすう域いき。如此則そく存在そんざい一いち個こ分解ぶんかい使し得とく

$M=U\Sigma V^{*},\,$

其中U是これm×m階かい酉とり矩のり陣じん；Σしぐま是ぜm×n階かい非負ひふ实数對たい角かく矩のり陣じん；而V*，即そくV的てき共軛きょうやく轉置てんち，是ぜn×n階かい酉とり矩のり陣じん。這樣的てき分解ぶんかい就稱作さくM的てき奇異きい值分解ぶんかい。Σしぐま對角線たいかくせん上じょう的てき元素げんそΣしぐま_i,i即そく為ためM的てき奇異きい值。

常見つねみ的てき做法是ぜ将はた奇異きい值由大だい而小排列はいれつ。如此Σしぐま便びん能のう由ゆかりM唯一ゆいいつ確定かくてい了りょう。（雖然U和わV仍然不能ふのう確定かくてい。）

直觀ちょっかん的てき解釋かいしゃく

在ざい矩のり陣じんM的てき奇異きい值分解ぶんかい中ちゅう

$M=U\Sigma V^{*},\,$

• V的てき列れつ（columns）組成そせい一いち套對$M\,$的てき正せい交「輸入ゆにゅう」或ある「分析ぶんせき」的てき基もと向むこう量りょう。這些向むこう量りょう是ぜ$M^{*}\,M$的てき特徵とくちょう向むこう量りょう。
• U的てき列れつ（columns）組成そせい一いち套對$M\,$的てき正せい交「輸出ゆしゅつ」的てき基もと向むこう量りょう。這些向むこう量りょう是ぜ$MM^{*}\,$的てき特徵とくちょう向むこう量りょう。
• Σしぐま對角線たいかくせん上じょう的てき元素げんそ是ぜ奇異きい值，可視かし為ため是ぜ在ざい輸入ゆにゅう與あずか輸出ゆしゅつ間あいだ進行しんこう的てき純量じゅんりょう的てき"膨脹ぼうちょう控ひかえ制せい"。這些是ぜ$MM^{*}\,$及$M^{*}\,M$的てき特とく征せい值的てき非ひ负平方根へいほうこん，並なみ與あずかU和わV的いくわ行ゆき向むこう量りょう相對そうたい應おう。

奇き异值和わ奇き异向量りょう，以及他た们与奇き异值分解ぶんかい的てき关系

一いち个非负实数すうσしぐま是ぜM的てき一いち个奇き异值仅当存在そんざいK^m的てき单位向むこう量りょうu和わKⁿ的てき单位向むこう量りょうv如下：

$Mv=\sigma u\,{\text{ and }}M^{*}u=\sigma v.\,\!$

其中向むこう量りょうu和わv分ぶん别为σしぐま的てき左ひだり奇き异向量りょう和わ右みぎ奇き异向量りょう。

对于任意にんい的てき奇き异值分解ぶんかい

$M=U\Sigma V^{*}\,\!$

矩のり阵Σしぐま的てき对角线上的てき元素げんそ等とう于M的てき奇き异值. U和わV的てき列れつ分ぶん别是奇き异值中ちゅう的てき左ひだり、右みぎ奇き异向量りょう。因よし此，上述じょうじゅつ定理ていり表明ひょうめい：

• 一いち个m×n的てき矩のり阵至多た有ゆうp = min(m,n)个不同ふどう的てき奇き异值；
• 总能在ざいK^m中ちゅう找到由ゆかりM的てき左ひだり奇き异向量りょう組成そせい的てき一いち組くみ正せい交基U，；
• 总能在ざいKⁿ找到由ゆかりM的てき右みぎ奇き异向量りょう組成そせい的てき一いち組くみ正せい交基V，。

如果對たい於一个奇异值，可か以找到两組线性無む关的左ひだり（右みぎ）奇異きい向こう量りょう，则該奇異きい值称为簡併的（或ある退化たいか的てき）。

非ひ退化たいか的てき奇き异值在ざい最多さいた相差おうさつ一いち個こ相しょう位い因子いんし$\exp(i\phi )$（若わか討論とうろん限定げんてい在ざい實數じっすう域いき內，則のり最多さいた相差おうさつ一いち個こ正負せいふ號ごう）的てき意義いぎ下か具有ぐゆう唯一ゆいいつ的てき左ひだり、右みぎ奇き异向量りょう。因よし此，如果M的てき所有しょゆう奇き异值都と是非ぜひ退化たいか且非零れい，則のり除去じょきょ一個可以同時乘在$U,V$上うえ的てき任意にんい的てき相しょう位い因子いんし外がい，$M$的てき奇異きい值分解ぶんかい唯一ゆいいつ。

根ね据すえ定てい义，退化たいか的てき奇き异值具有ぐゆう不ふ唯ただ一いち的てき奇き异向量りょう。因よし为，如果u₁和わu₂为奇异值σしぐま的てき两个左ひだり奇き异向量りょう，则它們的任意にんい歸き一化线性组合也是奇异值σ一个左奇异向量，右みぎ奇き异向量りょう也具有ぐゆう類似るいじ的てき性せい质。因よし此，如果M具有ぐゆう退化たいか的てき奇き异值，则它的てき奇き异值分解ぶんかい是ぜ不ふ唯ただ一いち的てき。

例れい子こ

观察一いち个4×5的てき矩のり阵

$M={\begin{bmatrix}1&0&0&0&2\\0&0&3&0&0\\0&0&0&0&0\\0&4&0&0&0\end{bmatrix}}$

M矩のり阵的奇き异值分解ぶんかい如下$U\Sigma V^{*}$

$U={\begin{bmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{bmatrix}},\;\Sigma ={\begin{bmatrix}4&0&0&0&0\\0&3&0&0&0\\0&0&{\sqrt {5}}&0&0\\0&0&0&0&0\end{bmatrix}},\;V^{*}={\begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\{\sqrt {0.2}}&0&0&0&{\sqrt {0.8}}\\0&0&0&1&0\\{\sqrt {0.8}}&0&0&0&-{\sqrt {0.2}}\end{bmatrix}}$

注意ちゅうい矩のり陣じん$\Sigma$的てき所有しょゆう非ひ對たい角かく元もと為ため0。矩のり阵$U$和わ$V^{*}$都みやこ是ただし酉とり矩のり阵，它們乘じょう上じょう各自かくじ的てき共軛きょうやく轉置てんち都と得え到いた單位たんい矩のり陣じん。如下所しょ示しめせ。在ざい这个例れい子中こなか，由ゆかり于$U$和わ$V^{*}$都みやこ是ただし实矩陣じん，故こ它們都と是ぜ正せい交矩阵。

$UU^{*}={\begin{bmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{bmatrix}}\cdot {\begin{bmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{bmatrix}}={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}}\equiv I_{4}$

$VV^{*}={\begin{bmatrix}0&0&{\sqrt {0.2}}&0&{\sqrt {0.8}}\\1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&0\\0&0&{\sqrt {0.8}}&0&-{\sqrt {0.2}}\end{bmatrix}}\cdot {\begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\{\sqrt {0.2}}&0&0&0&{\sqrt {0.8}}\\0&0&0&1&0\\{\sqrt {0.8}}&0&0&0&-{\sqrt {0.2}}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}}\equiv I_{5}$

由よし於$\Sigma$有ゆう一いち個こ對たい角かく元もと是ぜ零れい，故こ这个奇き异值分解ぶんかい值不是ぜ唯一ゆいいつ的てき。例れい如，选择$V$使つかい得とく

$V^{*}={\begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\{\sqrt {0.2}}&0&0&0&{\sqrt {0.8}}\\{\sqrt {0.4}}&0&0&{\sqrt {0.5}}&-{\sqrt {0.1}}\\-{\sqrt {0.4}}&0&0&{\sqrt {0.5}}&{\sqrt {0.1}}\end{bmatrix}}$

能のう得え到いた$M$的てき另一いち個こ奇異きい值分解ぶんかい。

与あずか特とく征せい值分解ぶんかい的てき联系

奇き异值分解能ぶんかいのう夠用于任意にんい$m\times n$矩のり阵，而特とく征せい分解ぶんかい只ただ能のう适用于特定とくてい类型的てき方かた阵，故こ奇異きい值分解ぶんかい的てき適用てきよう範圍はんい更さら廣ひろ。不ふ过，这两个分解ぶんかい之の间是有ゆう关联的てき。给定一いち个M的てき奇き异值分解ぶんかい，根ね据すえ上面うわつら的てき论述，两者的てき关系式しき如下：

$M^{*}M=V\Sigma ^{*}U^{*}\,U\Sigma V^{*}=V(\Sigma ^{*}\Sigma )V^{*}\,$

$MM^{*}=U\Sigma V^{*}\,V\Sigma ^{*}U^{*}=U(\Sigma \Sigma ^{*})U^{*}\,$

关系式しき的てき右みぎ边描述じゅつ了りょう关系式しき左ひだり边的特とく征せい值分解ぶんかい。于是：

• $V$的てき列れつ向むこう量りょう（右みぎ奇き异向量りょう）是これ$M^{*}M$的てき特とく征せい向こう量りょう。
• $U$的てき列れつ向むこう量りょう（左ひだり奇き异向量りょう）是これ$MM^{*}$的てき特とく征せい向こう量りょう。
• $\Sigma$的てき非ひ零れい對たい角かく元もと（非ひ零れい奇き异值）是これ$M^{*}M$或ある者もの$MM^{*}$的てき非ひ零れい特とく征せい值的てき平方根へいほうこん。

特殊とくしゅ情じょう况下，当とうM是ぜ一いち个正せい规矩阵（因いん而必須是方陣ほうじん）根ね据すえ谱定理ていり，M可か以被一组特征向量酉对角化，所以ゆえん它可以表为：

$M=UDU^{*}$

其中U为一个酉矩のり阵，D为一个对角かく阵。如果M是これ半はん正せい定じょう的てき，$M=UDU^{*}$的てき分解ぶんかい也是一いち个奇异值分解ぶんかい。

然しか而，一般矩陣的特征分解跟奇异值分解不同。特とく征せい分解ぶんかい如下：

$M=UDU^{-1}$

其中U是ぜ不ふ需要じゅよう是ぜ酉とり的てき，D也不需要じゅよう是ぜ半はん正せい定じょう的てき。而奇异值分解ぶんかい如下：

$M=U\Sigma V^{*}$

其中$\Sigma$是ぜ对角半はん正せい定てい矩のり阵，U和わV是ぜ酉とり矩のり阵，两者除じょ了りょう通どおり过矩阵M没ぼつ有ゆう必然ひつぜん的てき联系。

几何意い义

因いん为U和わV都みやこ是ただし酉とり的てき，我わが们知道どうU的てき列れつ向むこう量りょう u₁,...,u_m 组成了りょうK^m空そら间的一いち组标准正せい交基。同どう样，V的てき列れつ向むこう量りょうv₁,...,v_n也组成なり了りょうKⁿ空そら间的一组标准正交基（根ね据すえ向こう量りょう空そら间的标准点てん积法则）。

矩のり陣じん$M$代表だいひょう從したがえ$K^{n}$到いた$K^{m}$的てき一個線性映射${\mathcal {T}}$：$x\rightarrow Mx$。通過つうか这些标准正せい交基，这个变换可か以用很簡單かんたん的てき方式ほうしき進行しんこう描述：${\mathcal {T}}(v_{i})=\sigma _{i}u_{i},i=1,\ldots ,\min(m,n)$，其中$\sigma _{i}$是これ$\Sigma$中なか的てき第だいi个對角かく元もと。当とう$i>\min(m,n)$时，${\mathcal {T}}(v_{i})=0$。

这样，SVD分解ぶんかい的てき几何意い义就可か以做如下的てき归纳：对于每ごと一个线性映射${\mathcal {T}}:K^{n}\rightarrow K^{m}$，${\mathcal {T}}$的てき奇異きい值分解ぶんかい在原ありわら空間くうかん與あずか像ぞう空間くうかん中ちゅう分別ふんべつ找到一いち組くみ標準ひょうじゅん正せい交基，使つかい得とく${\mathcal {T}}$把わ$K^{n}$的てき第だい$i$個こ基もと向むこう量りょう映うつ射い為ため$K^{m}$的てき第だい$i$个基もと向むこう量りょう的てき非ひ负倍数すう，並なみ将しょう$K^{n}$中ちゅう余あまり下か的てき基もと向むこう量りょう映うつ射い为零向むこう量りょう。換かわ句く話はなし說せつ，線せん性せい變換へんかん${\mathcal {T}}$在ざい這兩組ぐみ選定せんてい的てき基もと上じょう的てき矩のり陣じん表示ひょうじ為ため所有しょゆう對たい角かく元もと均ひとし為ため非負ひふ數すう的てき對たい角かく矩のり陣じん。

SVD方法ほうほう種類しゅるい

GRSVD

GRSVD為ため其中一いち種しゅSVD分解ぶんかい方法ほうほう。他た利用りようhouseholder transformations將はた目標もくひょう矩のり陣じん轉換てんかん成なり雙そう斜はす對たい角かく矩のり陣じん，再さい利用りようQR algorithm追つい蹤其特徵とくちょう值。 此演算えんざん法的ほうてき限げん制せい為ため，難なん以估計けい出だし真正しんせい的てき準じゅん確かく值。根據こんきょ下圖したず所しょ示しめせ可か觀察かんさつ出で，iteration較大時じ會かい慢慢decay最後さいごerror會かい達たち到いた飽和ほうわ。

Jacobi SVD

一種いっしゅSVD方法ほうほう為ためJacobi SVD，此種方法ほうほう的てき複雜ふくざつ度ど較GRSVD高だか，但ただし是ぜ精確せいかく度ど也較高だか。Jacobi SVD使用しよう多た次つぎ的てき平面へいめん旋轉せんてん使し得とく矩のり陣じん上じょう非ひ對たい角かく軸じく上じょう的てき數すう值趨近きん於0。 於此，運用うんよう演算えんざん法ほう可か將はた矩のり陣じん轉換てんかん成なり我わが們所需的型式けいしき:

將はたA0轉換てんかん成なりA，成なり為ため只ただ有ゆう對角線たいかくせん有ゆう值的矩のり陣じん。 下圖したず為ためerror模擬もぎ圖ず，可か觀察かんさつ出で:iteration次數じすう增加ぞうか，可か以相對たい增加ぞうか其精準じゅん度ど。

应用

求もとめ广义逆ぎゃく阵（伪逆）

奇き异值分解ぶんかい可か以被用よう来らい计算矩のり阵的广义逆ぎゃく阵（伪逆）。若わか矩のり阵M的てき奇き异值分解ぶんかい为$M=U\Sigma V^{*}$，那な么M的てき伪逆为

$M^{+}=V\Sigma ^{+}U^{*},\,$

其中$\Sigma ^{+}$是これ$\Sigma$的てき偽にせ逆ぎゃく，是ぜ将しょう$\Sigma$主しゅ对角线上每ごと个非零れい元素げんそ都と求もとめ倒たおせ数すう之これ後ご再さい轉置てんち得え到いた的てき。求もとめ伪逆通常つうじょう可か以用来らい求もとめ解かい最小さいしょう二に乘法じょうほう问题。

列れつ空間くうかん、零れい空間くうかん和わ秩

奇き异值分解ぶんかい的てき另一个应用是给出矩阵的列れつ空間くうかん、零れい空間くうかん和わ秩的てき表示ひょうじ。对角矩のり阵$\Sigma$的てき非ひ零れい对角元素げんそ的てき个数对应于矩阵$M$的てき秩。與あずか零れい奇異きい值對應おう的てき右みぎ奇異きい向こう量りょう生成せいせい矩のり陣じん$M$的てき零れい空間くうかん，與あずか非ひ零れい奇異きい值對應おう的てき左ひだり奇異きい向こう量りょう則そく生成せいせい矩のり陣じん$M$的てき列れつ空間くうかん。在ざい线性代数だいすう數すう值計算けいさん中ちゅう奇き异值分解ぶんかい一般用于确定矩阵的有效秩，這是因いん為ため，由ゆかり於捨入にゅう誤差ごさ，秩虧矩のり陣じん的てき零れい奇異きい值可能會のうかい表現ひょうげん為ため很接近せっきん零れい的てき非ひ零れい值。

矩のり阵近似きんじ值

奇き异值分解ぶんかい在ざい统计中ちゅう的てき主要しゅよう应用为主成分しゅせいぶん分析ぶんせき（PCA）。数かず据すえ集しゅう的てき特とく征せい值（在ざいSVD中ちゅう用よう奇き异值表ひょう征せい）按照重要じゅうよう性せい排列はいれつ，降くだ维的过程就是舍しゃ弃不重要じゅうよう的てき特とく征せい向こう量的りょうてき过程，而剩下か的てき特とく征せい向こう量りょう张成空そら间为降维后的てき空そら间。

幾いく種しゅ程ほど式しき語ご言げん中ちゅう计算SVD的てき函はこ式しき範はん例れい

• Mathematica:

{U, Σしぐま, V}=SingularValueDecomposition[a]

• MATLAB：

[b c d]=svd(x)

• OpenCV:

void cvSVD( CvArr* A, CvArr* W, CvArr* U=NULL, CvArr* V=NULL, int flags=0 )

• Python（使用しようSciPy（页面存そん档备份，存そん于互联网档案あん馆）库）

U,s,Vh = scipy.linalg.svd(A)

• R:

S=svd(x)

历史

参まいり见

外部がいぶ链接

• LAPACK users manual （页面存そん档备份，存そん于互联网档案あん馆） gives details of subroutines to calculate the SVD (see also [1]（页面存そん档备份，存そん于互联网档案あん馆）).
• Applications of SVD on PC Hansen's web site.
• Introduction to the Singular Value Decomposition by Todd Will of the University of Wisconsin--La Crosse.
• Los Alamos group's book chapter（页面存そん档备份，存そん于互联网档案あん馆） has helpful gene data analysis examples.
• MIT Lecture（页面存そん档备份，存そん于互联网档案あん馆） series by Gilbert Strang. See Lecture #29 on the SVD.
• Java SVD library routine.
• Java applet demonstrating the SVD.
• Java script （页面存そん档备份，存そん于互联网档案あん馆） demonstrating the SVD more extensively, paste your data from a spreadsheet.
• Chapter from "Numerical Recipes in C"（页面存そん档备份，存そん于互联网档案あん馆） gives more information about implementation and applications of SVD.
• Online Matrix Calculator Performs singular value decomposition of matrices.

参考さんこう文献ぶんけん

• Demmel, J. and Kahan, W. (1990). Computing Small Singular Values of Bidiagonal Matrices With Guaranteed High Relative Accuracy. SIAM J. Sci. Statist. Comput., 11 (5), 873-912.
• Golub, G. H. and Van Loan, C. F. (1996). "Matrix Computations". 3rd ed., Johns Hopkins University Press, Baltimore. ISBN 0-8018-5414-8.
• Halldor, Bjornsson and Venegas, Silvia A. (1997). "A manual for EOF and SVD analyses of climate data"（页面存そん档备份，存そん于互联网档案あん馆）. McGill University, CCGCR Report No. 97-1, Montréal, Québec, 52pp.
• Hansen, P. C. (1987). The truncated SVD as a method for regularization. BIT, 27, 534-553.
• Horn, Roger A. and Johnson, Charles R (1985). "Matrix Analysis". Section 7.3. Cambridge University Press. ISBN 0-521-38632-2.
• Horn, Roger A. and Johnson, Charles R (1991). Topics in Matrix Analysis, Chapter 3. Cambridge University Press. ISBN 0-521-46713-6.
• Strang G (1998). "Introduction to Linear Algebra". Section 6.7. 3rd ed., Wellesley-Cambridge Press. ISBN 0-9614088-5-5.