奇异值分解

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

理论描述

假设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的一个奇异值仅当存在Km的单位向量u和Kn的单位向量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)个不同的奇异值;
  • 总能在Km中找到由M的左奇异向量组成的一组正交基U,;
  • 总能在Kn找到由M的右奇异向量组成的一组正交基V,。
    如果对于一个奇异值,可以找到两组线性无关的左(右)奇异向量,则该奇异值称为简并的(或退化的)。

非退化的奇异值在最多相差一个相位因子\exp(i\phi)(若讨论限定在实数域内,则最多相差一个正负号)的意义下具有唯一的左、右奇异向量。因此,如果M的所有奇异值都是非退化且非零,则除去一个可以同时乘在U,V上的任意的相位因子外,M的奇异值分解唯一。

根据定义,退化的奇异值具有不唯一的奇异向量。因为,如果u1和u2为奇异值σ的两个左奇异向量,则它们的任意归一化线性组合也是奇异值σ一个左奇异向量,右奇异向量也具有类似的性质。因此,如果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 是对角半正定矩阵,U和V是酉矩阵,两者除了通过矩阵M没有必然的联系。

应用

求广义逆阵(伪逆)

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

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

列空间、零空间和秩

奇异值分解的另一个应用是给出矩阵的列空间、零空间和秩的表示。对角矩阵\Sigma 的非零对角元素的个数对应于矩阵M的秩。与零奇异值对应的右奇异向量生成矩阵M的零空间,与非零奇异值对应的左奇异向量则生成矩阵M的列空间。在线性代数数值计算中奇异值分解一般用于确定矩阵的有效秩,这是因为,由于舍入误差,秩亏矩阵的零奇异值可能会表现为很接近零的非零值。

矩阵近似值

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程