特征抽取奇异值分解SVD | 彩潭有鲤的札记

特征值和特征向量

特征值和特征向量的定义如下：

是一个的实对称矩阵，是一个维向量，是矩阵的一个特征值，是特征值所对应的特征向量。

特征值和特征向量有什么好处呢？

可以将矩阵特征分解。如果求出了矩阵的个特征值以及这个特征值所对应的特征向量，若这个特征向量线性无关，那么矩阵就可以用下式的特征分解表示：

是这个特征向量所张成的维矩阵，为这个特征值为主对角线的维矩阵

一般会把的这个特征向量标准化，即满足，或者说，此时的个特征向量为标准正交基，满足，即, 也就是说为酉矩阵。

这样特征分解表达式可以写成：

注意：要进行特征分解，矩阵必须为方阵。那么如果不是方阵（行和列不相同）时，还可以对矩阵进行分解吗？答案是可以，此时SVD登场了。

SVD

SVD也是对矩阵进行分解，但是和特征分解不同，SVD并不要求要分解的矩阵为方阵。假设矩阵是一个的矩阵，那么定义矩阵的SVD为：

是一个的矩阵；是一个的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值；是一个的矩阵。

和都是酉矩阵，即满足。若限制，分解是唯一的。

下图可以很形象的看出上面SVD的定义：

如何求出SVD分解后的 这三个矩阵？

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

这样就可以得到矩阵的个特征值和对应的个特征向量。将的所有特征向量张成一个的矩阵，就是SVD公式里面的矩阵。一般将中的每个特征向量叫做的右奇异向量。

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

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

和都求出来了，就剩下奇异值矩阵了。由于除了对角线上是奇异值其他位置都是0，只需要求出每个奇异值就可以了。

注意到:

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

的特征向量组成的是矩阵，的特征向量组成的是矩阵，有什么根据吗？

很容易证明，以矩阵的证明为例：

上式证明使用了: 。可以看出的特征向量组成的的确就是SVD中的矩阵。类似的方法可以得到的特征向量组成的就是我们SVD中的矩阵。

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

这样也就是说：可以不用来计算奇异值，通过求出的特征值取平方根来求奇异值

SVD几何解释

表示了一个从维空间到维空间的一个线性变换

线性变换可以分解为三个简单的变换：

坐标系的旋转或反射变换，

坐标轴的缩放变换，

坐标系的旋转或反射变换，

SVD计算举例

这里用一个简单的例子来说明矩阵是如何进行奇异值分解的。

矩阵定义为：

首先求出:

进而求出的特征值和特征向量：

接着求的特征值和特征向量：

利用求奇异值：

当然，也可以用直接求出奇异值为和。

最终得到A的奇异值分解为：

SVD的一些性质

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

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

完全奇异值分解：

紧奇异值分解：设有实矩阵其秩为，则称为的紧奇异值分解

截断奇异值分解：只取最大的个奇异值 ( ，为矩阵的秩）对应的部分，就得到矩阵的截断奇异值分解。实际应用中提到矩阵的奇异值分解时，通常指截断奇异值分解。

紧奇异值分解对应着无损压缩，截断奇异值分解对应着有损压缩。

SVD用于PCA

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

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

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

假设样本是的矩阵，如果通过SVD找到了矩阵最大的个特征向量张成的维矩阵，则如果进行如下处理：

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

奇异值分解与矩阵近似

奇异值分解是在平方损失意义下对矩阵的最优近似

首先定义矩阵的平方损失函数（也称为弗罗贝尼乌斯范数）：

设矩阵，定义矩阵的平方损失函数为：

下面证明一个结论：

证明：

一般地，若是阶正交矩阵，则：

这是因为：

同理，若是阶正交矩阵，则：

因此：

即：

有了上述结论，接下来证明奇异值分解是在平方损失意义下对矩阵的最优近似。

定理1 设矩阵，设为中所有秩不超过的矩阵集合，，则存在一个秩为的矩阵，使得：，称矩阵为矩阵在平方误差下的最优近似。

定理2 设矩阵，有奇异值分解，并设为中所有秩不超过的矩阵的集合，，若秩为的矩阵满足：，则：

特别地，若，其中：

则：

原理