奇异值分解(SVD)原理

PCA回顾

在之前的文章中我们对PCA降维进行总结

Betten：主成分分析PCA学习总结​zhuanlan.zhihu.com

图标

下面我们回顾下算法流程：

输入：

[公式]

维样本集

[公式]

，要降维到的维数

[公式]

.

输出：降维后的样本集

[公式]

1.对所有的样本进行中心化

[公式]

2.计算样本的协方差矩阵

[公式]

3.求出协方差矩阵的特征值及对应的特征向量

4.将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵

[公式]

5.

[公式]

即为降维到

[公式]

维后的数据

考虑一个问题，假设样本集

[公式]

中每个

[公式]

是一个图片，并且是一个

[公式]

的图片，如果以像素值作为特征，那么每张图片的特征维度是10000。当进行PCA降维时，难点在于我们构造协方差矩阵时，维度达到

[公式]

。在这样的协方差矩阵上求解特征值，耗费的计算量程平方级增长。面对这样一个难点，从而引出奇异值分解(SVD)，利用SVD不仅可以解出PCA的解，而且无需大的计算量。

奇异值分解(singular value decomposition)

SVD的基本公式：

[公式]

其中，

[公式]

，

[公式]

，

[公式]

且除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，且已按大小拍好序，

[公式]

。其中，

[公式]

的列向量即是

[公式]

的特征向量，一般我们将

[公式]

中的每个特征向量叫做

[公式]

的左奇异向量；

[公式]

的列向量即是

[公式]

的特征向量，一般我们将

[公式]

中的每个特征向量叫做

[公式]

的右奇异向量。

[公式]

和

[公式]

我们都求出来了，现在就剩下奇异值矩阵

[公式]

没有求出了。

由于

[公式]

除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值

[公式]

就可以了。

我们注意到:

[公式]

这样我们可以求出我们的每个奇异值，进而求出奇异值矩阵

[公式]

。

上面还有一个问题没有讲，就是我们说

[公式]

的特征向量组成的就是我们SVD中的

[公式]

矩阵，而

[公式]

的特征向量组成的就是我们SVD中的

[公式]

矩阵，这有什么根据吗？这个其实很容易证明，我们以

[公式]

矩阵的证明为例。

[公式]

上式证明使用了

[公式]

。可以看出

[公式]

的特征向量组成的的确就是我们SVD中的

[公式]

矩阵。类似的方法可以得到

[公式]

的特征向量组成的就是我们SVD中的

[公式]

矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：

[公式]

这样也就是说，我们可以不用

[公式]

来计算奇异值，也可以通过求出

[公式]

的特征值取平方根来求奇异值。

性质

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

[公式]

个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说，可以对

[公式]

三个矩阵进行裁剪，比如将特征

[公式]

维降至

[公式]

维，那么

[公式]

，

[公式]

，

[公式]

即可。

由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。下面我们就对SVD用于PCA降维做一个介绍。

小结

SVD作为一个很基本的算法，在很多机器学习算法中都有它的身影，特别是在现在的大数据时代，由于SVD可以实现并行化，因此更是大展身手。SVD的原理不难，只要有基本的线性代数知识就可以理解，实现也很简单因此值得仔细的研究。当然，SVD的缺点是分解出的矩阵解释性往往不强，不过这不影响它的使用。

SVD最早的应用之一是信息检索，我们称利用SVD的方法为潜在语义索引(Latent Semantic Indexing ，LSI)或潜在语义分析(Latent Semantic Analysis ，LSA)。

SVD另一个应用为推荐系统应用，简单版本的推荐系统能够计算物品item或者用户user之间的相似度，可以用SVD将原始数据映射到低维空间中，然后节省计算相似度时的计算资源。

参考出处

斯坦福大学公开课_机器学习_奇异值分解

刘建平Pinard奇异值分解

《机器学习实战》