1 SVD 的介绍

假设 A 是一个 $n\times n$ 的方阵，则其具有如下形式：

$$A\nu =\lambda \nu$$

其中 $\lambda$ 是矩阵 A 的一个特征值， $\nu$ 是矩阵 A 的一个$n$ 维特征向量。若把矩阵 A 的 $n$ 个特征值及其对应的特征向量均求出，且按照特征值的大小由大到小排列，则其可以分解成如下形式：

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

其中 $W$ 是 $n$ 个单位特征向量构成的矩阵，则 $W{W}^T=I\Rightarrow W^T=W^{-1}$，因此上式可以转换成如下形式：

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

只有当矩阵 A 是方阵时才能对其进行特征值分解。若矩阵 A 是一个 $m\times n$ 的矩阵，在线性代数中可以对其进行奇异值分解（SVD），线性代数中定义 SVD 的分解形式如下：

$$A=U\Sigma V^T$$

其中 $U$ （左奇异矩阵）是一个 $m\times m$ 的方阵， $\Sigma$ 是一个 $m\times n$ 的矩阵， $V$ （右奇异矩阵）是一个 $n\times n$ 的方阵，且 $U{U}^T=I$ ,$V{V}^T=I$ 。接下来对求解 $U、\Sigma 、V$ 进行推导：
由于 $A^{T}A、A{A}^T$ 分别为 $n\times n、m\times m$ 的方阵，则根据特征值的分解原理，其可以分解成如下形式：

$$(A^{T}A)\nu =\lambda \nu$$

$$(A{A}^T)\mu =\lambda \mu$$

上述两式中的特征值相同，因为 $(AB)\alpha =\lambda \alpha \Rightarrow (BA)(B\alpha )=\lambda (B\alpha )$ ，则 $U$ 可以由特征向量 $\mu$ 构成， $V$ 可以由特征向量 $\nu$ 构成。由于 $\Sigma$ 除对角线上为奇异值外其他位置均为 0，假设其对角线上的奇异值为 $\sigma$，则其推导如下：

$$A=U\Sigma V^T\Rightarrow AV=U\Sigma V^{T}V\Rightarrow AV=U\Sigma \Rightarrow A\nu =\sigma \mu$$

其实也可以通过 $A^{T}A或A{A}^T$ 的特征值取平方根来求奇异值，本文以 $A^{T}A$ 为例，其推导过程如下：

$$A=U\Sigma V^T\Rightarrow A^T=V{\Sigma }^T{U}^T\Rightarrow A^{T}A=V{\Sigma }^T{U}^{T}U\Sigma V^T\Rightarrow A^{T}A=V({\Sigma }^T\Sigma )V^T$$

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

奇异值矩阵中的奇异值与特征分解中的特征值类似，其对角线上的奇异值也是按照从大到小排列，且奇异值的减小特别的快。在大多数情况下，前 $r$ 个奇异值（个数占比在前 10% 或者 1%）的和占全部奇异值之和的比例超过 99%，也就是说可以用前 $r$ 个奇异值和对应的左右奇异向量来近似描述矩阵。即：

$$A_{m\times n}=U_{m\times r}{\Sigma }_{r\times r}(V^T{)}_{r\times n}$$

其分解图形如下：

通过 SVD 分解，可以对高维数据进行降维去噪，因此其在降维算法中的特征分解、推荐系统及自然语言处理等领域均有应用，是很多机器学习算法的基石。

2 Python 中的实现

# 可以调用numpy中的linalg对矩阵进行奇异值分解
import numpy as np

A = np.mat([[1,2,3],[4,5,6]])
U,sigma,VT=np.linalg.svd(A)
U
matrix([[-0.3863177 , -0.92236578],
        [-0.92236578,  0.3863177 ]])
# 只返回非零奇异值,在应用中需要转化成相应维度的矩阵
sigma
array([9.508032  , 0.77286964])
VT
matrix([[-0.42866713, -0.56630692, -0.7039467 ],
        [ 0.80596391,  0.11238241, -0.58119908],
        [ 0.40824829, -0.81649658,  0.40824829]])

3 参考资料

推荐如下两篇本文参考的文章：
1 https://www.cnblogs.com/pinard/p/6251584.html
2 http://coldjune.com/2018/05/31/SVD/