奇异值分解

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

理論描述

假設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 的一个正交基U，组成M的左奇异向量。
• 总是可以找到和Kⁿ的一个正交基V，组成M的右奇异向量。

如果一个奇异值中可以找到两个左（或右）奇异向量是线性相关的，则称为退化。

非退化的奇异值具有唯一的左、右奇异向量，取决于所乘的单位相位因子e^iφ（根据实际信号）。因此，如果M的所有奇异值都是非退化且非零，则它的奇异值分解是唯一的，因为U中的一列要乘以一个单位相位因子且同时V中相应的列也要乘以同一个相位因子。

根据定义，退化的奇异值具有不唯一的奇异向量。因为，如果u₁和u₂为奇异值σ的两个左奇异向量，则两个向量的任意规范线性组合也是奇异值σ一个左奇异向量，类似的，右奇异向量也具有相同的性质。因此，如果M 具有退化的奇异值，则它的奇异值分解是不唯一的。

例子

观察一个4x5的矩阵

$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. 一个对角线元素是0. 并且,因为矩阵 $U$ 和$V^*$ 是 酉, 乘以各自个共轭系数并得出结果确定矩阵, 如下所示. 在这个例子中，由于 $U$ 和 $V^*$ 是实值, 他们各自是 正交矩阵.

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

and

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

必须注意的是这个奇异值分解值不是唯一的. 选择 $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×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^{*}$的特征向量。
• Σ（非零奇异值）的非零元素是$M^{*}M$或者$MM^{*}$中非零特征值的平方根。

特殊情况下，当M是一个正规矩阵，即是一个方阵时，根据谱定理，M可以被一组特征向量单一对角化，所以它可以被写为：

$M = U D U^*$

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

然而，在其他所有的M矩阵上，特征分解跟奇异值分解是不同。特征分解如下：

$M=UDU^{-1}$

其中U是不需要是单式的，D也不需要是正半定的。而奇异值分解如下：

$M=U\Sigma V^*$

其中Σ是对角半正定矩阵，U 和 V是酉矩阵，两者除了通过矩阵M没有必然的联系。

存在性

矩阵的特征值 λ具有如下关系 M u = λ u. 当 M 是 Hermitian, 特征值的取值是可以取得的 使得 M 为真 n × n symmetric matrix.定义 f :Rⁿ → R by f(x) = x^T M x.根据 extreme value theorem, 在一些u上，这个连续性函数可以取得最大值 当取得严格的限定{||x|| ≤ 1}. 根据 Lagrange multipliers 理论, u 是需要满足的

$\nabla f = \nabla \; x^T M x = \lambda \cdot \nabla \; x^T x,$

在这里 nabla 符号, $\nabla$, 是 del 算符.

简单的计算就可得到 M u = λ u (对称性 M是必须的). 因此 λ 是最大的特征值 M.相同的计算值表明正交分量 u 给于第二大的特征值. ; 这里f(x) = x* M x2n 是一个真值相关的 真变量.

基于谱定理

使得 M是一个m-by-n具有复杂特性的矩阵. M*M 是半正定和hermitian. 根据 spectral theorem, 这里存在 一个 unitary n-by-n 句子 V有如下

$V^* M^* M V = \begin{bmatrix} D & 0 \\ 0 & 0\end{bmatrix}$

这里D是一个对角 和正定. 恰当的划分 V 我们有

$\begin{bmatrix} V_1 ^* \\ V_2 ^*\end{bmatrix} M^* M \begin{bmatrix} V_1 & V_2 \end{bmatrix} = \begin{bmatrix} V_1 ^* M^* M V_1 & V_1 ^* M^* M V_2 \\ V_2 ^* M^* M V_1 & V_2 ^* M^* M V_2 \end{bmatrix} = \begin{bmatrix} D & 0 \\ 0 & 0\end{bmatrix}.$

因此 V₁*M*MV₁ = D and V₂*M*MV₂ = 0. The latter means MV₂ = 0.

由于 V 是 unitary, V₁*V₁ = I, V₂*V₂ = I and V₁V₁* + V₂V₂* = I.

定义

$U_1 = M V_1 D^{-1/2}.\!$

于是有

$U_1 D^{1/2} V_1^* = M V_1 D^{-1/2} D^{1/2} V_1^* = M . \,$

这是我们想要的结果, 除了 U₁ and V₁ 不是 unitary , 但仅仅isometries. 为了解决问题 我们简单的得到"fill out" 这些矩阵获得 unitaries. 例如, 我们可以选择U₂ 因此

$U = \begin{bmatrix} U_1 & U_2 \end{bmatrix}$

是 unitary.

定义

$\Sigma = \begin{bmatrix} \begin{bmatrix} D^{1/2} & 0 \\ 0 & 0\end{bmatrix} \\ 0 \end{bmatrix}$

这里多余的0行是加进去的或者删除的使零行数等于列数 U₂. 由此

$\begin{bmatrix} U_1 & U_2 \end{bmatrix} \begin{bmatrix} \begin{bmatrix} D^{1/2} & 0 \\ 0 & 0\end{bmatrix} \\ 0 \end{bmatrix} \begin{bmatrix} V_1 & V_2 \end{bmatrix}^* = \begin{bmatrix} U_1 & U_2 \end{bmatrix} \begin{bmatrix} D^{1/2} V_1^* \\ 0 \end{bmatrix} = U_1 D^{1/2} V_1^* = M ,$

这是想要的结果:

$M = U \Sigma V^* .\!$

注意该参数可以开始对角化 MM* 而不是 M*M (这显示 MM* and M*M 具有相同的非0特征值).

基于变特性

这个单一值可以定义为 u^TMv, 考虑到函数 u and v, 在一个特别的子空间上. 这个向量代表这u and v 在这里m是可以获取的 使得 M 代表m × n 带有实值的矩阵. Let $S^{m-1}$ and $S^{n-1}$ 代表这二维向量的集合 R^m and Rⁿ各自的. 定义函数

$\sigma(u,v) = u^{T} M v \,$

有向量 u ∈ $S^{m-1}$和v ∈ $S^{n-1}$. 考虑函数 σ restricted to $S^{m-1}$ × $S^{n-1}$. 由于两个 $S^{m-1}$ 和$S^{n-1}$ 是 compact 集合, 他们的 product 也是相关的. 并且, 既然 σ是连续的, 他获得一个最大值，至少是一对向量值 u ∈ $S^{m-1}$ and v ∈ $S^{n-1}$. 这个最大值 σ₁ 相关向量是 u₁ 和 v₁. 既然 $\sigma_{1}$ 是最大值$\sigma(u,v)$ 这个是非负的. 如果是负的, 改变符号u₁ or v₁ 将使得变正和变得更大.

状态: u₁, v₁ 是左右奇异向量 M 和相关的向量 σ₁.

证明:与特征值例子类似, 假设两个向量满足拉格朗日乘子方程:

$\nabla \sigma = \nabla \; u^T M v = \lambda_1 \cdot \nabla \; u^T u + \lambda_2 \cdot \nabla \; v^T v.$

经过代数变换, 就成为

$M v_{1} = 2 \lambda_{1} u_{1} + 0, \,$

and

$M^{T} u_{1} = 0 + 2 \lambda_{2} v_{1}. \,$

乘以从左边的第一个方程$u_{1}^{T}$ 和左边的第二个方程 $v_{1}^{T}$ and taking ||u|| = ||v|| = 1 一起来考虑

$u_{1}^{T} M v_{1} = \sigma_{1} = 2 \lambda_{1},$

$v_{1}^{T} M^{T} u_{1} = \sigma_{1} = 2 \lambda_{2}.$

So σ₁ = 2 λ₁ = 2 λ₂. 函数特性 φ defined by

$\phi(w) = u_1 ^T w, \,$

我们有

$M v_{1} = \sigma_{1} u_{1}. \,$

相似的

$M^{T} u_{1} = \sigma_{1} v_{1}. \,$

这证明了以下条目

更多的单一向量和单一值是建立在以下最大值 σ(u, v) 常规化 u, v这个正交于u₁ and v₁, 各自的. 这个实值对复数值是特征值的相似例子

几何意义

因为U 和V 向量都是单位化的向量, 我们知道U的列向量u₁,...,u_m组成了K^m空间的一组标准正交基。同样，V的列向量v₁,...,v_n也组成了Kⁿ空间的一组标准正交基(根据向量空间的标准点积法则).

线性变换T: Kⁿ → K^m，把向量x变换为Mx。考虑到这些标准正交基，这个变换描述起来就很简单了: T(v_i) = σ_i u_i, for i = 1,...,min(m,n), 其中σ_i 是对角阵Σ中的第i个元素; 当i > min(m,n)时，T(v_i) = 0。

这样，SVD理论的几何意义就可以做如下的归纳：对于每一个线性映射T: Kⁿ → K^m，T把Kⁿ的第i个基向量映射为K^m的第i个基向量的非负倍数,然后将余下的基向量映射为零向量。对照这些基向量，映射T就可以表示为一个非负对角阵。

范数

1. 矩阵范数的概念 设A∈Cm×n，定义一个实值函数||A||，若满足：

(1) 非负性：||A||≥0，且||A||=0当且仅当A=0； (2) 齐次性：||aA||=|a| ||A||，a∈C； (3) 三角不等式：||A+B||≤||A||+||B||，A,B∈ Cm×n; (4) 相容性：||AB||≤||A|| ||B||

则称||A||为A的矩阵范数。 例1 设A=(aij)∈Cn×n，则

都是

定理2：由向量的1-范数、2-范数和∞-范数分别诱导出的矩阵范数分别是

通常依次称为列和范数、谱范数和行和范数。

定理3：谱范数和F-范数都是酉不变范数，即对于任意酉矩阵P和Q，有||PAQ||=||A||。

应用

求伪逆

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

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

其中 Σ⁺ 是将Σ转置，并将其主对角线上每个非零元素都求倒数得到的。求伪逆通常可以用来求解线性最小平方问题。

平行奇异值模型

把频率选择性衰落信道进行分解.

矩阵近似值

奇异值分解在统计中的主要应用为主成分分析（PCA），种数据分析方法，用来找出大量数据中所隐含的“模式”,它可以用在模式识别，数据压缩等方面。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 )

外部链接

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