奇异值分解

维基百科,自由的百科全书
跳转至: 导航搜索
线性代数
\mathbf{A} = \begin{bmatrix}
1 & 2 \\
3 & 4 \end{bmatrix}
向量 · 矩阵  · 行列式  · 线性空间

奇异值分解(singular value decomposition)是线性代数中一种重要的矩阵分解,在信号处理统计学等领域有重要应用。奇异值分解在某些方面与对称矩阵Hermite矩阵基于特征向量对角化类似。然而这两种矩阵分解尽管有其相关性,但还是有明显的不同。对称阵特征向量分解的基础是谱分析,而奇异值分解则是谱分析理论在任意矩阵上的推广。

理論描述[编辑]

假設M是一個m×n矩陣,其中的元素全部屬於K,也就是實數域或複數域。如此則存在一個分解使得

M = U  \Sigma V^*, \,

其中Um×m酉矩陣;Σ是半正定m×n实数對角矩陣;而V*,即V共軛轉置,是n×n階酉矩陣。這樣的分解就稱作M奇異值分解。Σ對角線上的元素Σi,i即為M奇異值

常見的做法是将奇異值由大而小排列。如此Σ便能由M唯一確定了。(雖然UV仍然不能確定。)

直觀的解釋[编辑]

在矩陣M的奇異值分解中

M = U\Sigma V^*, \,
  • V的列(columns)組成一套對M\,正交"輸入"或"分析"的基向量。這些向量是M^*\,M特徵向量
  • U的列(columns)組成一套對M\,正交"輸出"的基向量。這些向量是MM^*\,特徵向量
  • Σ對角線上的元素是奇異值,可視為是在輸入與輸出間進行的純量的"膨脹控制"。這些是MM^*\,M^*\,M特征值的非零平方根,並與UV的行向量相對應。

奇异值和奇异向量,以及他们与奇异值分解的关系[编辑]

一个非负实数σ是M的一个奇异值仅当存在Km的单位向量uKn的单位向量v如下:

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

其中向量uv分别为σ的左奇异向量和右奇异向量。

对于任意的奇异值分解

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

矩阵Σ的对角线上的元素等于M的奇异值. UV的列分别是奇异值中的左、右奇异向量。因此,上述定理表明:

  • 一个m×n的矩阵至少有一个最多有p = min(m,n)个不同的奇异值;
  • 总能在Km中找到由M的左奇异向量組成的一組正交基U,;
  • 总能在Kn找到由M的右奇异向量組成的一組正交基V,。

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

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

根据定义,退化的奇异值具有不唯一的奇异向量。因为,如果u1u2为奇异值σ的两个左奇异向量,则它們的任意歸一化线性组合也是奇异值σ一个左奇异向量,右奇异向量也具有類似的性质。因此,如果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。矩阵UV^*都是酉矩阵,它們乘上各自的共軛轉置都得到單位矩陣。如下所示。在这个例子中,由于UV^*都是实矩陣,故它們都是正交矩阵

 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
 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.

由於\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^{*}\,

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

关系式的右边描述了关系式左边的特征值分解。于是:

  • V的列向量(右奇异向量)是M^{*}M特征向量
  • U的列向量(左奇异向量)是MM^{*}的特征向量。
  • \Sigma的非零對角元(非零奇异值)是M^{*}M或者MM^{*}的非零特征值的平方根。

特殊情况下,当M是一个正规矩阵(因而必須是方陣)根据谱定理M可以被一组特征向量酉对角化,所以它可以表为:

M = U D U^*

其中U为一个酉矩阵,D为一个对角阵。如果M半正定的,M = U D U^*的分解也是一个奇异值分解。

然而,一般矩陣的特征分解跟奇异值分解不同。特征分解如下:

M=UDU^{-1}

其中U是不需要是酉的,D也不需要是半正定的。而奇异值分解如下:

M=U\Sigma V^*

其中\Sigma是对角半正定矩阵,UV是酉矩阵,两者除了通过矩阵M没有必然的联系。

几何意义[编辑]

因为UV都是酉的,我们知道U的列向量u1,...,um组成了Km空间的一组标准正交基。同样,V的列向量v1,...,vn也组成了Kn空间的一组标准正交基(根据向量空间的标准点积法则)。

矩陣M代表從K^nK^m的一個線性映射\mathcal Tx\rightarrow Mx。通過这些标准正交基,这个变换可以用很簡單的方式進行描述:\mathcal T(v_i)=\sigma_iu_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 TK^n的第i個基向量映射為K^m的第i基向量的非负倍数,並将K^n中余下的基向量映射为零向量。換句話說,線性變換\mathcal T在這兩組選定的基上的矩陣表示為所有對角元均為非負數的對角矩陣。

应用[编辑]

求伪逆[编辑]

奇异值分解可以被用来计算矩阵的伪逆。若矩阵M的奇异值分解为 M = U\Sigma V^*,那么M的伪逆为

 M^+ = V \Sigma^+ U^*, \,

其中\Sigma^+\Sigma的偽逆,是将\Sigma主对角线上每个非零元素都求倒数之後再轉置得到的。求伪逆通常可以用来求解最小二乘法问题。

列空間、零空間和秩[编辑]

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

矩阵近似值[编辑]

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

幾種程式語言中计算SVD的函式範例[编辑]

  • matlab:
[b c d]=svd(x)
  • OpenCV:
void cvSVD( CvArr* A, CvArr* W, CvArr* U=NULL, CvArr* V=NULL, int flags=0 )

历史[编辑]

参见[编辑]

外部链接[编辑]

参考文献[编辑]

  • 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.