奇异值分解（singular value decomposition，简称SVD）不仅广泛应用于机器学习领域，也在控制理论中有着广泛的应用。本文主要介绍SVD的基本原理。

一、预备知识

1.1 特征值与特征向量

设 A 是n阶方阵，如果存在数λ和非零n维列向量 x，使得 $A\alpha =\lambda \alpha$ 成立，则称 λ 是矩阵A的一个特征值（characteristic value)，而α是矩阵A对应于特征值λ的特征向量（Eigenvector）。

1.2 幺正矩阵（酉矩阵）（Unitary Matrix）

泛泛来讲，如果一个n阶方阵,它的列向量构成一组标准正交基,那么这个矩阵就是幺正矩阵，或称酉矩阵。

一个简单的充分必要判别准则是：方阵U的共扼转置乘以U等于单位阵，则U是酉矩阵。即酉矩阵的逆矩阵与其伴随矩阵相等。

对于实数矩阵而言，共轭转置等于其转置。

酉矩阵的性质：

① 矩阵U为酉矩阵的充要条件是它的共轭转置矩阵等于其逆矩阵，
即 $U^{\ast }=U^{-1}$ 或 $U^{\ast }U=U{U}^{\ast }=I$

② 若酉矩阵的元素全是实数，则其为正交矩阵；
正交矩阵的性质：转置等于伴随，即$U^T=U^{\ast }$

③ 酉矩阵的行列式的绝对值为1；
④ U=VΣV*
其中V是酉矩阵，Σ 是主对角线上元素绝对值为1的对角阵。

在查找相关文献时，遇到了一个问题：共轭转置矩阵与伴随矩阵为什么都用A*表示？
关于详细解答，请参考：https://zhuanlan.zhihu.com/p/87330558

这里只总结一句：当A为酉矩阵时，伴随矩阵等于其共轭转置矩阵。

1.3 特征分解

求出特征值和特征向量之后，就可以对方阵A进行特征分解。

$A=W\Sigma W^{-1}$

其中W是这n个特征向量所张成的n x n维酉矩阵（$W^T=W^{-1}$），Σ 是主对角线上每个元素就是一个特征值的对角阵。

因此也可以写成：$A=W\Sigma W^T$

分解得到的 Σ 矩阵是一个对角阵， 里面的特征值是由大到小排列的， 这些特征值所对应的特征向量就是描述这个矩阵变化方向（从主要的变化到次要的变化排列）。

【总结】： 特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要， 而特征向量表示这个特征是什么。不过， 特征值分解也有很多的局限， 比如说要进行特征分解，矩阵A必须是方阵。如果A不是方阵，即行和列不相同时，就不能用这种方法对矩阵进行分解，由此引入SVD的概念。

二、SVD定义

SVD也是对矩阵进行分解，但是与特征分解不同，SVD并不要求分解的矩阵为方阵。
定义矩阵A的SVD为：

$A=U\Sigma V^T$

其中U是一个m * m的矩阵，Σ是一个m * n的矩阵，除了对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，V是一个n * n的矩阵。U和V都是酉矩阵，即满足$U^{T}U=I$，$V^{T}V=I$

那么我们如何求出SVD分解后的U，Σ，V这三个矩阵呢？

2.1 求矩阵V

将矩阵A的转置与A作矩阵乘法，得到一个n x n的方阵$A^{T}A$。由于$A^{T}A$是方阵，因此可以进行特征分解，而且得到特征值λ_i与特征向量v_i。将该方阵的所有特征向量张成一个n x n的矩阵V，这就是SVD中的矩阵V了。

一般，将V中的每个特征向量叫做A的右特征向量。

2.2 求矩阵U

相反，将矩阵A与A的转置作矩阵乘法，得到一个m x m的方阵$A{A}^T$。由于$A{A}^T$是方阵，因此可以进行特征分解，而且得到特征值λ_i与特征向量u_i。将该方阵的所有特征向量张成一个n x n的矩阵U，这就是SVD中的矩阵U了。

一般，将U中的每个特征向量叫做A的左特征向量。

2.3 求矩阵Σ

$A=U\Sigma V^T\Rightarrow AV=U\Sigma V^{T}V\Rightarrow AV=U\Sigma \Rightarrow A{v}_i={\sigma }_i{u}_i\Rightarrow {\sigma }_i=A{v}_i/u_i$

或$A={\lambda }_1{u}_1(v_1{)}^T+{\lambda }_2{u}_2(v_2{)}^T+...$

通过上式就可以求出每个奇异值σ_i，进而求出奇异值矩阵Σ。

【证明】：
因为：$U^{T}U=I$，${\Sigma }^T\Sigma ={\Sigma }^2$
故
$A=U\Sigma V^T\Rightarrow AT=V{\Sigma }^T{U}^T\Rightarrow A^{T}A=V{\Sigma }^T{U}^{T}U\Sigma V^T=V{\Sigma }^2{V}^T$

由此可以看出，A^TA的特征向量组成的的确是V矩阵，同理也可证明U矩阵。
同时，我们发现，特征值矩阵等于奇异值矩阵的平方，也可以说：

${\sigma }_i=\sqrt{{\lambda }_i}$

这也是一个十分有用的公式。

2.4 奇异值

A的正奇异值个数等于rank(A), 并且A与AH有相同的奇异值。

奇异值$\sigma$跟特征值类似，在矩阵$\Sigma$中也是从大到小排列，而且$\sigma$的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r（r远远小于m、n）个的奇异值来近似描述矩阵，即部分奇异值分解：
$A_{m\times n}=U_{m\times r}{\Sigma }_{r\times r}{V}_{r\times n}^T$

右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，当r越接近于n，则相乘的结果越接近于A。

三、SVD计算举例

例：求矩阵A=$\left(\begin{array}{lcr}1& 0& 0\\ 2& 0& 0\end{array}\right)$ 的奇异值分解。

解：我们首先求出A^TA和AA^T：
$A^{T}A=\left(\begin{array}{lc}1& 2\\ 0& 0\\ 0& 0\end{array}\right)\left(\begin{array}{lcr}1& 0& 0\\ 2& 0& 0\end{array}\right)=\left(\begin{array}{lcr}5& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right)$，

$A{A}^T=\left(\begin{array}{lcr}1& 0& 0\\ 2& 0& 0\end{array}\right)\left(\begin{array}{lc}1& 2\\ 0& 0\\ 0& 0\end{array}\right)=\left(\begin{array}{lc}1& 2\\ 2& 4\end{array}\right)$，

根据特征值：λ₁=5，λ₂=λ₃=0对应的特征向量为：
v₁=[1,0,0]^T，v₂=[0,1,0]^T，v₃=[0,0,1]^T
从而$V=\left(\begin{array}{lcr}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$，

根据特征值：λ₁=5，λ₂=0对应的特征向量为：
u₁=[$1/\sqrt{5},2/\sqrt{5}$]^T，u₂=[$-2/\sqrt{5},1/\sqrt{5}$]^T

从而$U=\left(\begin{array}{lc}1/\sqrt{5}& -2/\sqrt{5}\\ 2/\sqrt{5}& 1/\sqrt{5}\end{array}\right)$。

根据非零特征值λ₁=5，则A的奇异值为σ₁=$\sqrt{5}$,故D=$\sqrt{5}$。
最终得到A的奇异值分解：
$A=U\Sigma V^T=U\left(\begin{array}{lcr}\sqrt{5}& 0& 0\\ 0& 0& 0\end{array}\right)V^T=\left(\begin{array}{lc}1/\sqrt{5}& -2/\sqrt{5}\\ 2/\sqrt{5}& 1/\sqrt{5}\end{array}\right)\left(\begin{array}{lcr}\sqrt{5}& 0& 0\\ 0& 0& 0\end{array}\right)\left(\begin{array}{lcr}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$

四、MATLAB仿真训练

MATLAB提供了svd函数用于奇异值分解，其代码如下：

A=[1,0,0;2,0,0];
[U,S,V]=svd(A)

输出结果：

五、SVD应用

5.1 奇异值分解可以降维

M表示n个n维向量，可以通过奇异值分解表示成m+n个r维向量，若A的秩r远远小于m和n，则通过奇异值分解可以降低A的维数。可以计算出，当$r<\frac{mn}{m+n+1}$时，可以达到降维的目的， 同时可以降低计算机对存贮器的要求。

5.2 奇异值对矩阵的扰动不敏感

特征值对矩阵的扰动敏感。
在数学上可以证明， 奇异值的变化不会超过相应矩阵的变化。

六、SVD优势

SVD为什么值得这么关注呢？
我们来看一个引例：

奇异值分解可用于高效地表示数据。例如，假设我们希望传输以下图像，该图像由15个25个黑色或白色像素的阵列组成。

由于该图像中只有三种类型的列，如下所示，因此应该可以以更紧凑的形式表示数据。

这样就大大减少了要记录的数据数量。

七、小结

SVD作为一个很基本的算法，在机器学习和控制理论等领域有着广泛的应用。
当然，SVD的缺点是分解出的矩阵解释性往往不强，有点黑盒子的味道，不过这不影响它的使用。

参考：http://www.ams.org/publicoutreach/feature-column/fcarc-svd