奇异值分解

奇异值分解（英語：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}$的一個線性映射解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“http://localhost:6011/zh.wikipedia.org/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\displaystyle \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分解方法。他利用豪斯霍尔德变换將目標矩陣轉換成雙斜對角矩陣，再利用QR algorithm追蹤其特徵值。 此演算法的限制為，難以估計出真正的準確值。根據下圖所示可觀察出，误差会随着迭代次数增加而减小，最终达到饱和。

Jacobi SVD

一種SVD方法為Jacobi SVD，此種方法的複雜度較GRSVD高，但是精確度也較高。Jacobi SVD使用多次的平面旋轉使得矩陣上非對角軸上的數值趨近於0。 於此，運用演算法可將矩陣轉換成我們所需的型式:

將A0轉換成A，成為只有對角線有值的矩陣。 下圖為误差模擬圖，可觀察出迭代次數增加，可以相對增加其精準度。

应用

求广义逆阵（伪逆）

奇异值分解可以被用来计算矩阵的广义逆阵（伪逆）。若矩阵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.