查看“︁奇异值分解”︁的源代码

{{Multiple issues|
{{Cleanup|time=2024-07-15T08:29:26+00:00}}
{{Copy edit|time=2024-07-15T08:29:26+00:00}}
}}
{{NoteTA |G1=Math}}
{{线性代数}}
'''奇异值分解'''（{{Lang-en|Singular value decomposition}}，縮寫：'''SVD'''）是[[线性代数]]中一种重要的[[矩阵分解]]，在[[信号处理]]、[[统计学]]等领域有重要应用。奇异值分解在某些方面与[[對稱矩陣|对称矩阵]]或[[埃尔米特矩阵]]基于[[特征向量]]的[[对角化]]类似，这两种矩阵分解尽管有其相关性，但还是有明显的不同。对称阵特征向量分解的基础是[[谱分析]]，而奇异值分解则是谱分析理论在任意矩阵上的推广。

== 理論描述 ==
假設''M''是一個''m×n''階[[矩陣]]，其中的元素全部屬於[[域 (数学)|域]]''K''，也就是[[實數]]域或[[复数 (数学)|複數]]域。如此則存在一個分解使得
:<math>M = U  \Sigma V^*, \,</math>
其中''U''是''m×m''階[[酉矩陣]]；Σ是''m×n''階非負[[实数]][[對角矩陣]]；而''V*''，即''V''的[[共軛轉置]]，是''n×n''階[[酉矩阵|酉矩陣]]。這樣的分解就稱作''M''的'''奇異值分解'''。Σ對角線上的元素Σ<sub>''i'',''i''</sub>即為''M''的'''奇異值'''。

若将对角线元素相同但排列顺序不同的Σ视为等价，Σ由''M''唯一確定。（雖然''U''和''V''仍然不能確定。） 

===直觀的解釋===
在矩陣''M''的奇異值分解中
: <math>M = U\Sigma V^*, \,</math>
* ''V''的列（columns）組成一套對<math>M\,</math>的[[正交]]「輸入」或「分析」的[[基向量]]。這些向量是<math>M^*\,M</math>的[[特徵向量]]。
* ''U''的列（columns）組成一套對<math>M\,</math>的[[正交]]「輸出」的[[基向量]]。這些向量是<math>MM^*\,</math>的[[特徵向量]]。
* Σ對角線上的元素是[[奇異值]]，可視為是在輸入與輸出間進行的純量的"膨脹控制"。這些是<math>MM^*\,</math>及<math>M^*\,M</math>的[[特征值]]的非负平方根，並與''U''和''V''的行向量相對應。

== 奇异值和奇异向量，以及他们与奇异值分解的关系 ==
一个非负实数σ是''M''的一个[[奇异值]]仅当存在''K''<sup>''m''</sup>的单位向量''u''和''K''<sup>''n''</sup>的单位向量''v''如下：
:<math>Mv = \sigma u \,\text{ and } M^{*}u= \sigma v. \,\!</math>
其中向量''u''和''v''分别为σ的左奇异向量和右奇异向量。

对于任意的奇异值分解
:<math>M = U\Sigma V^{*} \,\!</math>
矩阵Σ的对角线上的元素等于''M''的奇异值. ''U''和''V''的列分别是奇异值中的左、右奇异向量。因此，上述定理表明：
*一个m×n的矩阵至多有''p''&nbsp;= min(''m'',''n'')个不同的奇异值；
*总能在''K''<sup>''m''</sup>中找到由''M''的左奇异向量組成的一組[[正交基]]''U''，；
*总能在''K''<sup>''n''</sup>找到由''M''的右奇异向量組成的一組正交基''V''，。 

如果對於一个奇异值，可以找到两組线性無关的左（右）奇異向量，则該奇異值称为簡併的（或退化的）。

非退化的奇异值在最多相差一個相位因子<math>\exp(i\phi)</math>（若討論限定在實數域內，則最多相差一個正負號）的意義下具有唯一的左、右奇异向量。因此，如果''M''的所有奇异值都是非退化且非零，則除去一個可以同時乘在<math>U,V</math>上的任意的相位因子外，<math>M</math>的奇異值分解唯一。

根据定义，退化的奇异值具有不唯一的奇异向量。因为，如果''u''<sub>1</sub>和''u''<sub>2</sub>为奇异值σ的两个左奇异向量，则它們的任意歸一化线性组合也是奇异值σ一个左奇异向量，右奇异向量也具有類似的性质。因此，如果''M''具有退化的奇异值，则它的奇异值分解是不唯一的。

== 例子 ==
观察一个4×5的矩阵

:<math>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}
</math>

M矩阵的奇异值分解如下<math>U \Sigma V^*</math>

:<math>
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}
</math>

注意矩陣<math>\Sigma</math>的所有非對角元為0。矩阵<math>U</math>和<math>V^*</math>都是[[酉矩阵]]，它們乘上各自的共軛轉置都得到[[單位矩陣]]。如下所示。在这个例子中，由于<math>U</math>和<math>V^*</math>都是实矩陣，故它們都是[[正交矩阵]]。

:<math> U  U^* =
\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
</math>

:<math> V  V^* =
\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
</math>

由於<math>\Sigma</math>有一個對角元是零，故这个奇异值分解值不是唯一的。例如，选择<math>V</math>使得
:<math>
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}
</math>
能得到<math>M</math>的另一個奇異值分解。

== 与特征值分解的联系 ==
奇异值分解能夠用于任意<math>m\times n</math>矩阵，而[[特征分解]]只能适用于特定类型的方阵，故奇異值分解的適用範圍更廣。不过，这两个分解之间是有关联的。给定一个''M''的奇异值分解，根据上面的论述，两者的关系式如下：
:<math>
M^{*} M = V \Sigma^{*} U^{*}\, U \Sigma V^{*} =
V (\Sigma^{*} \Sigma) V^{*}\,
</math>

:<math>
M M^{*} = U \Sigma V^{*} \, V \Sigma^{*} U^{*} =
U (\Sigma \Sigma^{*}) U^{*}\,
</math>
 
关系式的右边描述了关系式左边的特征值分解。于是：
*<math>V</math>的列向量（右奇异向量）是<math>M^{*}M</math>的[[特征向量]]。
*<math>U</math>的列向量（左奇异向量）是<math>MM^{*}</math>的特征向量。
*<math>\Sigma</math>的非零對角元（非零奇异值）是<math>M^{*}M</math>或者<math>MM^{*}</math>的非零[[特征值]]的平方根。

特殊情况下，当''M''是一个[[正规矩阵]]（因而必須是方陣）根据[[谱定理]]，''M''可以被一组特征向量酉对角化，所以它可以表为：
:<math>M = U D U^*</math>
其中''U''为一个酉矩阵，''D''为一个对角阵。如果''M''是[[半正定]]的，<math>M = U D U^*</math>的分解也是一个奇异值分解。

然而，一般矩陣的特征分解跟奇异值分解不同。特征分解如下：
:<math>M=UDU^{-1}</math>
其中''U''是不需要是酉的，''D''也不需要是半正定的。而奇异值分解如下：
:<math>M=U\Sigma V^*</math>
其中<math>\Sigma</math>是对角半正定矩阵，''U''和''V''是酉矩阵，两者除了通过矩阵''M''没有必然的联系。

== 几何意义 ==
因为''U''和''V''都是酉的，我们知道''U''的列向量 ''u''<sub>1</sub>,...,''u<sub>m</sub>'' 组成了''K''<sup>''m''</sup>空间的一组[[标准正交基]]。同样，''V''的列向量''v''<sub>1</sub>,...,''v<sub>n</sub>''也组成了''K''<sup>''n''</sup>空间的一组标准正交基（根据向量空间的标准点积法则）。

矩陣<math>M</math>代表從<math>K^n</math>到<math>K^m</math>的一個線性映射<math>\mathcal T</math>：<math>x\rightarrow Mx</math>。通過这些标准正交基，这个变换可以用很簡單的方式進行描述：<math>\mathcal T(v_i)=\sigma_iu_i,i= 1,\ldots,\min(m,n)</math>，其中<math>\sigma_i</math>是<math>\Sigma</math>中的第''i''个對角元。当<math>i>\min(m,n)</math>时，<math>\mathcal T(v_i)=0</math>。

这样，SVD分解的几何意义就可以做如下的归纳：对于每一个线性映射<math>\mathcal T:K^n\rightarrow K^m</math>，<math>\mathcal T</math>的奇異值分解在原空間與像空間中分別找到一組標準正交基，使得<math>\mathcal T</math>把<math>K^n</math>的第<math>i</math>個基向量映射為<math>K^m</math>的第<math>i</math>个[[基向量]]的非负倍数，並将<math>K^n</math>中余下的基向量映射为零向量。換句話說，線性變換<math>\mathcal T</math>在這兩組選定的基上的矩陣表示為所有對角元均為非負數的對角矩陣。

== SVD方法種類 ==
; GRSVD
GRSVD為其中一種SVD分解方法。他利用[[豪斯霍尔德变换]]將目標矩陣轉換成雙斜對角矩陣，再利用QR algorithm追蹤其特徵值。
此演算法的限制為，難以估計出真正的準確值。根據下圖所示可觀察出，误差会随着迭代次数增加而减小，最终达到饱和。
[[File:Number of iterations.png|thumb|居中]]

; Jacobi SVD
一種SVD方法為Jacobi SVD，此種方法的複雜度較GRSVD高，但是精確度也較高。Jacobi SVD使用多次的平面旋轉使得矩陣上非對角軸上的數值趨近於0。
於此，運用演算法可將矩陣轉換成我們所需的型式:
[[File:2Jacobi SVD.png|500px|无框|居中]]
將A0轉換成A，成為只有對角線有值的矩陣。
下圖為误差模擬圖，可觀察出迭代次數增加，可以相對增加其精準度。
[[File:Number of sweeps.png|thumb|居中]]


== 应用 ==

=== 求广义逆阵（伪逆） ===

奇异值分解可以被用来计算矩阵的[[广义逆阵|广义逆阵（伪逆）]]。若矩阵''M''的奇异值分解为<math> M = U\Sigma V^*</math>，那么''M''的伪逆为

:<math> M^+ = V \Sigma^+ U^*, \,</math>
其中<math>\Sigma^+</math>是<math>\Sigma</math>的偽逆，是将<math>\Sigma</math>主对角线上每个非零元素都求倒数之後再轉置得到的。求伪逆通常可以用来求解[[最小二乘法]]问题。

=== 列空間、零空間和秩 ===
奇异值分解的另一个应用是给出矩阵的[[行空間與列空間|列空間]]、[[零空間]]和[[秩 (线性代数)|秩]]的表示。对角矩阵<math>\Sigma</math>的非零对角元素的个数对应于矩阵<math>M</math>的秩。與零奇異值對應的右奇異向量[[线性生成空间|生成]]矩陣<math>M</math>的零空間，與非零奇異值對應的左奇異向量則生成矩陣<math>M</math>的列空間。在线性代数數值計算中奇异值分解一般用于确定矩阵的有效秩，這是因為，由於捨入誤差，秩虧矩陣的零奇異值可能會表現為很接近零的非零值。

=== 矩阵近似值 ===

奇异值分解在统计中的主要应用为[[主成分分析]]（PCA）。数据集的特征值（在SVD中用奇异值表征）按照重要性排列，降维的过程就是舍弃不重要的特征向量的过程，而剩下的特征向量张成空间为降维后的空间。

== 幾種程式語言中计算SVD的函式範例 ==
*Mathematica:
:<code>{U, Σ, V}=SingularValueDecomposition[a]

*MATLAB：
:<code>[b c d]=svd(x)</code>

*OpenCV:
:<code>void cvSVD( CvArr* A, CvArr* W, CvArr* U=NULL, CvArr* V=NULL, int flags=0 )</code>

*Python（使用[https://www.scipy.org/ SciPy]{{Wayback|url=https://www.scipy.org/ |date=20170908150655 }}库）
:<code>U,s,Vh = scipy.linalg.svd(A)</code>

*R:
:<code>S=svd(x)</code>

== 历史 ==

== 参见 ==

== 外部链接 ==
* [http://www.netlib.org/lapack/lug/node53.html LAPACK users manual ]{{Wayback|url=http://www.netlib.org/lapack/lug/node53.html |date=20060524222756 }} gives details of subroutines to calculate the SVD (see also [http://www.netlib.org/lapack/lug/node32.html]{{Wayback|url=http://www.netlib.org/lapack/lug/node32.html |date=20060501053434 }}).
* [https://web.archive.org/web/20050820034632/http://www2.imm.dtu.dk/~pch/Projekter/tsvd.html Applications of SVD] on PC Hansen's web site.
* [https://web.archive.org/web/20060421024156/http://www.uwlax.edu/faculty/will/svd/ Introduction to the Singular Value Decomposition] by Todd Will of the University of Wisconsin--La Crosse.
* [http://public.lanl.gov/mewall/kluwer2002.html Los Alamos group's book chapter]{{Wayback|url=http://public.lanl.gov/mewall/kluwer2002.html |date=20060614101841 }} has helpful gene data analysis examples.
* [http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/index.htm MIT Lecture]{{Wayback|url=http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/index.htm |date=20060423213229 }} series by Gilbert Strang. See Lecture #29 on the SVD.
* [https://web.archive.org/web/20060313144512/http://www.idiom.com/~zilla/Computer/Javanumeric/index.html Java SVD] library routine.
* [https://web.archive.org/web/20051222074050/http://klebanov.homeip.net/~pavel/fb/java/la_applets/SVD/index.html Java applet] demonstrating the SVD.
* [http://users.pandora.be/paul.larmuseau/SVD.htm Java script ]{{Wayback|url=http://users.pandora.be/paul.larmuseau/SVD.htm |date=20060628091908 }} demonstrating the SVD more extensively, paste your data from a spreadsheet.
* [http://www.library.cornell.edu/nr/bookcpdf/c2-6.pdf Chapter from "Numerical Recipes in C"]{{Wayback|url=http://www.library.cornell.edu/nr/bookcpdf/c2-6.pdf |date=20060506170611 }} gives more information about implementation and applications of SVD.
* [https://web.archive.org/web/20081212221215/http://www.bluebit.gr/matrix-calculator/ 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). [http://www.vedur.is/~halldor/TEXT/eofsvd.html "A manual for EOF and SVD analyses of climate data"]{{Wayback|url=http://www.vedur.is/~halldor/TEXT/eofsvd.html |date=20050224035201 }}. 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.
{{泛函分析}}
[[Category:矩阵分解|Q]]
[[Category:时间序列降维方法]]