奇异值分解(SVD)

奇异值分解(Singular Value Decomposition, SVD)是在机器学习领域广泛使用的算法, 本文是对SVD原理的一个梳理和总结, 并讨论在 PCA 降维算法中是如何运用 SVD 的.

1. 特征值分解(EVD)

首先回顾下特征值和特征向量的定义如下:

$$Ax = \lambda x$$

其中, $A$ 是一个 $n\times n$ 的矩阵, $x$ 是一个 $n$ 维向量, $\lambda$ 是矩阵 $A$ 的一个特征值, 而 $x$ 是矩阵 $A$ 的特征值 $\lambda$ 所对应的特征向量.

方阵 $A_{n\times n}$ 可以做特征值分解的 充要条件 是其具有 $n$ 个线性无关的特征向量. 即 $A_{n\times n}$ 有 $n$ 个线性无关的特征向量时, $A_{n\times n}$ 才可以做特征值分解.

当我们求出了矩阵 $A$ 的 $n$ 个特征值 $\lambda_1 \leq \lambda_2 \leq … \leq \lambda_n$, 以及这 $n$ 个特征值所对应的特征向量 $w_1, w_2, …, w_n$, 我们就可以将矩阵 $A$ 分解成下面的形式:

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

其中, $W$ 是这 $n$ 个特征向量组成的 $n\times n$ 维矩阵, 而 $\Sigma$ 为这 $n$ 个特征值为主对角线的 $n\times n$ 维矩阵. 一般我们都会把 $W$ 的这 $n$ 个特征向量标准化, 即满足 $| w_i|_2 = 1$, 或者 $w_i^T w_i = 1$, 此时 $W$ 的 $n$ 个特征向量为标准正交基, 满足 $W^T W = I$, 即 $W^T = W^{-1}$, 也就是说 $W$ 为正交阵. 这样我们的特征分解表达式可以进一步写成:

$$A = W\Sigma W^T$$

这里注意, 要进行特征分解, 矩阵 $A$ 必须是 方阵. 如果不是方阵, 即行和列不同时, 就需要使用奇异值分解(SVD).

2. SVD 的定义

SVD 也是对矩阵进行分解, 但是和特征分解不同, SVD 并不要求分解的矩阵为方阵. 假设我们的矩阵 A 是一个 $m\times n$ 的矩阵, 那么我们定义矩阵 $A$ 的 SVD 为:

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

其中 $U$ 是一个 $m \times m$ 的矩阵, $\Sigma$ 是一个 $m\times n$ 的矩阵, 除了主对角线上的元素以外全为 0, 主对角线上的每个元素都称为奇异值, $V$ 是一个 $n \times n$ 的矩阵, $U$ 和 $V$ 都是正交矩阵, 既满足 $U^T U = I$, $V^T V = I$, 下图可以很形象的看出 SVD 的分解状态.

那么我们如何求出 SVD 分解后的 $U$, $\Sigma$, $V$ 这三个矩阵呢?

如果我们将 $A$ 的转置和 $A$ 做矩阵乘法, 那么就会得到一个 $n\times n$ 的方阵 $A^T A$, 由于 $A^T A$ 是方阵, 那么我们进而可以进行特征值分解(假设条件已经满足), 得到的特征值和特征向量如下式:

$$(A^T A)v_i = \lambda_i v_i$$

这样我们就可以得到矩阵 $A^T A$ 的 $n$ 个特征值和对应的 $n$ 个特征向量 $v_i$ 了. 然后将 $A^T A$ 的所有特征向量组织成一个 $n\times n$ 的矩阵 $V$, 该矩阵就是我们 SVD 公式里面的 $V$ 矩阵了, 一般我们将 $V$ 中的特征向量叫做 $A$ 的右奇异向量.

反过来, 如果我们将 $A$ 和 $A$ 的转置做矩阵乘法, 那么会得到一个 $m \times m$ 的方阵 $AA^T$, 同理, 我们可以对其进行特征分解, 得到的特征值和特征向量如下:

$$(AA^T) u_i = \lambda_i u_i$$

这样我们就得到了矩阵 $AA^T$ 的 $m$ 个特征值和对应的 $m$ 个特征向量 $u_i$. 同理, 我们将 $AA^T$ 的所有特征向量组织成一个 $m\times m$ 的矩阵 $U$, 该矩阵就是我们 SVD 公式里面的 $U$ 矩阵了. 一般我们将 $U$ 中的特征向量叫做 $A$ 的左奇异向量.

到现在为止, $U$ 和 $V$ 我们都求出来了, 现在就剩下奇异值矩阵 $\Sigma$ 没有求出了. 由于 $\Sigma$ 除了对角线上是奇异值, 其他位置都是0, 那么我们只需要求出每个奇异值 $\sigma$ 就可以了. 我们注意到:

$$A = U\Sigma V^T \Longrightarrow AV = U\Sigma V^T V \Longrightarrow AV = U\Sigma \Sigma \Longrightarrow Av_i = \sigma_i u_i \Longrightarrow \sigma_i = Av_i / u_i$$

根据上市我们就可以求出每个奇异值, 进而求出奇异值矩阵 $\Sigma$.

上面还有一个问题没有讲, 就是我们说 $A^T A$ 的特征向量组成的就是 SVD 的 V 矩阵, 而 $A A^T$ 的特征向量组成的矩阵 SVD 中的 $U$ 矩阵. 这有什么根据吗? 实际上, 证明如下(以 $V$ 为例):

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

上面的证明过程使用了 $U^T U = I$, 和 $\Sigma^T = \Sigma$ 两个性质. 进一步还可以看出特征值矩阵等于奇异值矩阵的平方, 就是说特征值和奇异值满足以下关系:

$$\sigma_i = \sqrt{\lambda_i}$$

通过上式, 我们可以不用 $\sigma_i = \frac{Av_i}{u_i}$ 来计算奇异值, 也可以通过求出 $A^T A$ 的特征值取平方根来求奇异值.

3. SVD 计算举例

4. SVD 的一些性质

对于奇异值, 它跟特征值分解中的特征值类似, 在奇异值矩阵中也是按照从大到小排列, 而且奇异值的下降速度很快, 在很多情况下, 前 10% 甚至 1% 的奇异值的和就站了全部奇异值之和的 99% 以上的比例. 也就是说, 我们可以用最大的 $k$ 个奇异值和对应的左右奇异值向量来近似描述矩阵, 即:

$$A_{m\times n} = U_{m\times m} \Sigma_{m\times n} V^T_{n\times n} \approx U_{m\times k} \Sigma_{k\times k} V^T_{k\times n}$$

其中, $k$ 要比 $\min(m, n)$ 小很多, 也就是一个大的矩阵 $A$ 可以用三个小的矩阵 $U_{m\times k} \Sigma_{k\times k} V^T_{k\times n}$ 来表示. 如下图所示, 矩阵 $A$ 只需要棕色部分的三个小矩阵就可以近似描述了.(在 Fast R-CNN 中对全连接层的矩阵使用了该方法降维).

由于这个重要的性质, SVD 可以很自然的用来进行 PCA 降维, 数据压缩和去噪.

1. SVD 用于 PCA

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

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

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

假设我们的样本是 $m\times n$的矩阵 $X$，如果我们通过 SVD 找到了矩阵 $XX^{T}$ 最大的 $d$ 个特征向量张成的 $m\times d$ 维矩阵 $U$，则我们如果进行如下处理：可以得到一个 $d\times n$ 的矩阵 $X’$,这个矩阵和我们原来的 $m\times n$ 维样本矩阵 $X$ 相比，行数从 $m$ 减到了 $k$，可见对行数进行了压缩。
左奇异矩阵可以用于行数的压缩。
右奇异矩阵可以用于列数即特征维度的压缩，也就是我们的PCA降维。

6. SVD 小结

SVD 作为一个很基本的算法, 在很多机器学习算法中都有它的身影, 特别是在现在的大数据时代, 由于 SVD 可以实现并行化, 因此更是大展身手. SVD 的 缺点 是分解出的矩阵解释性往往不强, 有点黑盒子的味道, 不过这不影响它的使用.