type
status
date
slug
summary
tags
category
icon
password
Property
原理
特征值和特征向量
特征值和特征向量的定义如下:
是一个的实对称矩阵,是一个维向量,是矩阵的一个特征值,是特征值所对应的特征向量。
特征值和特征向量有什么好处呢?
可以将矩阵特征分解。如果求出了矩阵的个特征值以及这个特征值所对应的特征向量,若这个特征向量线性无关,那么矩阵就可以用下式的特征分解表示:
是这个特征向量所张成的维矩阵,为这个特征值为主对角线的维矩阵
一般会把的这个特征向量标准化,即满足 ,或者说 ,此时的个特征向量为标准正交基,满足,即, 也就是说为酉矩阵。
这样特征分解表达式可以写成:
注意:要进行特征分解,矩阵必须为方阵。那么如果不是方阵(行和列不相同)时,还可以对矩阵进行分解吗?答案是可以,此时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 设矩阵 ,有奇异值分解 ,并设 为中所有秩不超过的矩阵的集合, ,若秩为 的矩阵满足: ,则:
特别地,若 ,其中:
则: