奇异值分解（SVD）算法笔记

奇异值分解（Singular Value Decomposition，后面简称 SVD）是在线性代数中一种重要的矩阵分解，它不光可用在降维算法中（例如 PCA 算法）的特征分解，还可以用于推荐系统，以及自然语言处理等领域，在机器学习，信号处理，统计学等领域中有重要应用。

基变换与特征值分解

基变换：数据与一个基做内积运算，结果作为第一个新的坐标分量，然后与第二个基做内积运算，结果作为第二个新坐标的分量。

PS：可看这里补充线性代数的基本知识

特征分解和奇异值分解（SVD）的区别

特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征。

所有的矩阵都可以进行奇异值分解，但只有方阵才可以进行特征值分解。当所给的矩阵是对称的方阵，AT=A，二者的结果是相同的。也就是说对称矩阵的特征值分解是所有奇异值分解的一个特例。但是二者还是存在一些小的差异，奇异值分解需要对奇异值进行从大到小的排序，而且全部是大于等于零。

对于如上的奇异值分解公式，我们可以看到奇异值分解同时包含了旋转，缩放和投影三种作用，并且 U 和 V 都起到了对 A 进行旋转的作用，而 Σ 起到了对 A 缩放的作用，特征值分解只有缩放的效果。

在应用上，奇异值分解主要用于数据矩阵，而特征值分解主要用于方型的相关矩阵。

SVD 的理论描述

假设 A 是一个 $m*n$ 阶矩阵，其中的元素全部属于域 K，也就是实数域或复数域。如此则存在一个分解使得：

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

其中 U 是 $m*m$ 阶酋矩阵，$\Sigma$ 是半正定 $m*n$ 阶对角矩阵，而 $V^T$ 是 $V$ 的共轭转置，是 $n*n$ 阶酋矩阵，这样的分解就称作 M 的奇异值分解。

$\Sigma$（是对角矩阵，但不一定是方阵）对角线上的元素 $\Sigma_i$ 即为 M 的奇异值。

一般的 $\Sigma$ 有如下形式：

$$\Sigma=\left[\begin{array}{ccccc} \sigma_{1} & 0 & 0 & 0 & 0 \\ 0 & \sigma_{2} & 0 & 0 & 0 \\ 0 & 0 & \ddots & 0 & 0 \\ 0 & 0 & 0 & \ddots & 0 \end{array}\right]_{m \times n}$$

上述分解中会构建出一个矩阵 $\Sigma$ ，该矩阵只有对角元素，其他元素均为 0，另一个惯例是，$Sigma$ 的对角元素是从大到小排列的。这些对角元素称为奇异值。在科学和工程中，一直存在这个一个普遍事实：在某个奇异值的数目（r 个）之后，其他奇异值都置为零，这就意味着数据集中仅有 r 个重要特征，其余的都是噪声或冗余数据。

求解

如果我们将 A 的转置和 A 做矩阵乘法，那么会得到 $n*n$ 的一个方阵 $A^TA$。既然 $A^TA$ 是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：

$$\left(A^{T} A\right) v_{i}=\lambda_{i} v_{i}$$

这样我们就可以得到矩阵 $A^TA$ 的 n 个特征值和对应的 n 个特征向量 v 了。将 $A^TA$ 的所有特征向量张成一个 $n*n$ 的矩阵 V，就是我们 SVD 公式里面的 V 矩阵了。一般我们将 V 中的每个特征向量叫做 A 的右奇异向量。

如果我们将 A 和 A 的转置做矩阵乘法，那么会得到 $m*m$ 的一个方阵 $AA^T$。 既然 $AA^T$ 是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下面公式：

$$\left(A A^{T}\right) u_{i}=\lambda_{i} u_{i}$$

这样我们就可以得到矩阵 $AA^T$ 的 m 个特征值和对应的 m 个特征向量 u 了。将 $AA^T$ 的所有特征张成一个 $m*m$ 的矩阵 U，就是我们 SVD 公式里面的 U 矩阵了。一般我们将 U 中的每个特征向量叫做 A 的左奇异向量。

由于 $\Sigma$ 除了对角线上是奇异值其他位置都是 0，所以我们只需要求出每个奇异值 $\sigma$ 就可以了。

注意有：

$$\begin{aligned} A &= U \Sigma V^{T} \\ \Rightarrow A V &= U \Sigma V^{T} V \\ \Rightarrow A V &= U \Sigma \\ \Rightarrow A v_{i} &= \sigma_{i} u_{i} \\ \Rightarrow \sigma_{i} &= A v_{i} / u_{i} \end{aligned}$$

上面还有一个问题就是我们说 $A^TA$ 的特征向量组成的就是我们 SVD 中的 V 矩阵，而 $AA^T$ 的特征向量组成的就是我们 SVD 中的 U 矩阵，这有什么根据吗？这个其实很容易证明，我们以 V 矩阵的证明为例：

$$\begin{aligned} & A=U \Sigma V^{T} , A^{\mathrm{T}}=V \Sigma U^{T} \\ \Rightarrow & A^{\mathrm{T}} A=V \Sigma U^{T} U \Sigma V^{T}=V \Sigma \Sigma V^{T}=V \Sigma^{2} V^{T} \\ \\ &A =U \Sigma V^{T} , A^{T}=V \Sigma^{T} U^{T} \\ \Rightarrow & A A^{T}=U \Sigma V^{T} V \Sigma^{T} U^{T}=U \Sigma^{T} \Sigma U^{T}=U \Sigma^{2} U^{T} \end{aligned}$$

其中：$U^TU = I, \Sigma^T\Sigma = \Sigma^2$

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方：

$$\sigma_{i}=\sqrt{\lambda_{i}}$$

这样也就是说，我们可以不用上面推导的式子来计算奇异值，我们可以直接通过求 ATA 的特征值取平方根来求奇异值。

注意 1：通过 $A^TA$ 的特征值取平方根求解奇异值的注意点

需要注意的是：这里的 $\Sigma\Sigma^T$ 和 $\Sigma^T\Sigma$ 在矩阵的角度上来讲，他们是不相等的，因为他们的维度不同 $\Sigma\Sigma^T \in R^{m*m}$，而 $\Sigma^T\Sigma \in R^{n*n}$ ，但是他们在主对角线的奇异值是相等的，即有：

$$\Sigma \Sigma^{T}=\left[\begin{array}{cccc} \sigma_{1}^{2} & 0 & 0 & 0 \\ 0 & \sigma_{2}^{2} & 0 & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & \ddots \end{array}\right]_{m \times m} \quad \Sigma^{T} \Sigma=\left[\begin{array}{cccc} \sigma_{1}^{2} & 0 & 0 & 0 \\ 0 & \sigma_{2}^{2} & 0 & 0 \\ 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & \ddots \end{array}\right]_{n \times n}$$

所以对于 $\Sigma\Sigma^T$ 和 $\Sigma^T\Sigma$ 中的特征值开方，可以得到所有的奇异值。

SVD 的几何层面理解

下面从几何层面上去理解二维的 SVD：对于任意的 2*2 矩阵，通过 SVD 可以将一个互相垂直的网络（orthogonal grid）变换到另外一个互相垂直的网络。

SVD 的推导

SVD 的一些性质

对于奇异值，它和我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的块，在很多情况下，前 10% 甚至 1% 的奇异值的和就占了全部的奇异值之和的 99% 以上的比例。也就是说，我们可以用最大的 k 个奇异值和对应的左右奇异值向量来近似描述矩阵。也就是说：

$$A_{m \times n}=U_{m \times m} \Sigma_{m \times n} V_{m \times n}^{T} \approx U_{m \times k} \Sigma_{k \times k} V_{k \times n}^{T}$$

由于奇异值的特点就是衰减特别快，也就是说仅仅有前几个奇异值特别大，后面的值都很小，这一点可以用于数据压缩和去噪，PCA 降维，也可以用于推荐算法，将用户和喜好对应的矩阵分解，进而得到隐含的用户需求来做推荐。

SVD 算法的应用

异值分解在统计中的主要应用为主成分分析（PCA），一种数据分析方法，用来找出大量数据中所隐含的 “模式”，PCA 算法的作用是把数据集映射到低维空间中去。数据集的特征值（在 SVD 中用奇异值表征）按照重要性排列，降维的过程就是舍弃不重要的特征向量的过程，而剩下的特征向量组成的空间即为降维后的空间。

在 PCA 降维中，需要找到样本协方差矩阵 XTX 的最大的 d 个特征向量，然后用这最大的 d 个特征向量张成的矩阵来做低维投影降维。可以看出，在这个过程中需要先求出协方差矩阵 XTX，当样本数多样本特征数也多的时候，这个计算量是很大的。

注意到 SVD 也可以得到协方差矩阵 XTX 最大的 d 个特征向量张成的矩阵，但是 SVD 有个好处，有一些 SVD 的实现算法可以不先求出协方差矩阵 XTX ，也能求出我们的右奇异矩阵 V。也就是说，我们的 PCA 算法可以不用做特征分解，而是做 SVD 来完成。这个方法在样本量很大的时候很有效。实际上，scikit-learn 算法的背后真正的实现就是 SVD，而不是我们认为的暴力特征分解。

另一方面，注意到 PCA 仅仅使用了我们 SVD 的右奇异矩阵，没有使用左奇异矩阵，那么左奇异矩阵有什么用呢？

假设我们那的样本是 mn 的矩阵 X，如果我们通过 SVD 找到了 矩阵 XXT 最大的 d 个特征向量张成的 md 维矩阵 U，则我们如果进行如下处理：

$$X_{d \times n}^{\prime}=U^{T}{ }_{d \times m} X_{m \times n}$$

可以得到一个 dn 的矩阵 X'，这个矩阵和我们原来的 mn 维样本矩阵 X 相比，行数从 m 减到了 d，可见对行数进行了压缩，也就是说，左奇异矩阵可以用于行数的压缩。相对的，右奇异矩阵可以用于列数集特征维度的压缩，也就是我们的 PCA 降维。

利用 Python 实现 SVD 降维

Python 中的 Numpy 包内有一个 linalg 的线性工具，可以使用它来直接计算 SVD 的结果