本文共 5643 字,大约阅读时间需要 18 分钟。
文章目录
-
写在前面
1. 从几何变换到奇异值分解
2. 代数角度理解奇异值与奇异向量
2.1 从正交基映射推导SVD
2.2 特征值分解求解奇异值和奇异向量
2.2.1 求解过程
2.2.2 推论
2.3 SVD的另一种形式
3. 几何角度理解奇异值与奇异向量
3.1 从坐标变换理解
3.1.1 从例子到一般
3.1.2 两个问题
3.2 形变的角度理解奇异值
4. 奇异值的最好解读
5. 特征值分解和奇异值分解区别
6. 奇异值分解在PCA中的应用
参考文献
广告
写在前面
读完本篇文章后,你应该可以知道:
奇异值分解到底是什么?
奇异值和奇异向量有什么代数意义?奇异值和奇异向量有什么几何意义?如何利用特征值分解求奇异值和奇异向量?奇异值的个数如何确定?奇异值分解是否唯一?奇异值分解什么时候和特征值分解相等?奇异值分解和特征值分解的区别?
1. 从几何变换到奇异值分解
这部分的内容是[1]中部分内容的翻译,这几张图片大家应该见过很多次。
来看一个二维平面坐标系的例子,在由(1,0)T和(0,1)T确定的二维平面坐标系中:
向量(x,y)T左乘M矩阵,将会得到一个新的向量(新的点)。为了更容易理解变换过程,我们主要关注向量(1,1)T和(1,0)T,(0,1)T,(0,0)T围城的矩形的形变过程。左乘矩阵M的效果在坐标系中的表现如下:直接从图上看不出什么,我们把原先的坐标系逆时针旋转30度,然后左乘M看看效果:好像也没什么特殊的,把原先的坐标系逆时针旋转60度看看:
右边的网格几乎快要正交了,也就是说,原先的正交基逆时针旋转60度后,再经过M变换,几乎可以得到一组新的正交基。实际上,如果我们把坐标轴逆时针旋转58.28度,就会得到如下效果:
从几何上看,旋转后的正交基(1,0)T和(0,1)T,在经过M变换后,得到了另外一组正交基。这其实就是SVD分解的一种解释,即M可以将一组正交基映射到另一组正交基。记映射后的向量Mv1为u1,Mv2为u2,Mv1的模为σ1,Mv2的模为σ2。接下来我们就可以推导了:在v1和v2确定的二维平面中,任意一点x可以表示为:
在《利用SVD进行推荐(1)矩阵相乘的本质》中我们讲过,小括号里的点积就是x在v1和v1坐标轴上的投影值(坐标)。我们对这个平面中任意一点x左乘矩阵M进行变换,来看看结果:向量点积表示为矩阵乘法就是:所以变换结果可以进一步推演为:我们得到了M有关u,v,σ的表达式。将表达式转为矩阵表达形式,即为:其中U中的每一列向量ui为映射后的一个单位基向量,V中的每一个列向量vj为原先被映射的单位基向量。这里的推导过于简略,下面我们看看更为严格的推导。2. 代数角度理解奇异值与奇异向量
奇异值分解在代数上表现就是A将一组正交基转化为另一组正交基。我们来看一下具体推导。
2.1 从正交基映射推导SVD
2.1内容主要来自[5],靖王你真帅!
假设找到了这样一组正交基:
而mxn的实矩阵A将其映射为:
我们要使他们两两正交,也就是:根据假设,有:在这种情况下,如果取vi为AT的特征向量的话,那么就有:这样我们就找到了正交基使其映射后还是正交基了。现在我们将映射后的正交基单位化。因为:也就是:所以取单位向量为:
由此可得:从上述公式来看,左奇异向量ui是映射后正交基的单位化形式,奇异值σi就是映射后的正交基的模的大小,而右奇异向量vi就是被映射的正交基。此处也可以看出奇异值一定非负(当然本身的定义就是这样)。当k < i < m时,对u1,u2,…,uk进行扩展u(k+1),…,um,使得u1,u2,…,um为m维空间中的一组正交基,即:
同样的,对v1,v2,…,vk进行扩展v(k+1),…,vn(这n-k个向量存在于A的零空间中,即Ax=0的解空间的基),使得v1,v2,…,vn为n维空间中的一组正交基,即:
然后我们就可以得到:从而A的SVD分解为:
根据论文[3]的分析,任意mxn的实矩阵A=UΣVT,都可以看成一种线性转化, 从n维空间到m维空间的转化。n维空间和m维空间分别由V和U的列向量所形成的基向量确定。
2.2 特征值分解求解奇异值和奇异向量
2.2.1 求解过程
对任意mxn实矩阵A的奇异值分解A=USVT,有:
ATA = VSTSVT(AAT)vi = VSTSVTvi=σi2vi这不就是特征值分解吗。也就是说vi是ATA的特征向量,其对应的特征值是σi2,同理ui是AAT的特征向量,其对应的特征值也是σi2。可以从这个角度出发求解特征值和特征向量。实际上,对于mxn维的实矩阵A,AAT和ATA都是半正定的实对称矩阵(特征值为非负数),且具有相同的非零特征值。且k=rank(AAT)=rank(ATA)=rank(A)[4]。显然实对称矩阵的秩就是非零特征值的个数。因此这两个实对称矩阵有k个相同的非零特征值。当i>rank(A)即使有特征值也全是0。
这里的分析还可以解释2.1中对角阵S上的i为什么最多取到k=rank(A),假设可以取到k+1,按照本节中的推导,奇异值σi+1是找不到对应的非零特征值的,显然σi+1=0。
或者说得专业些,ATA是实对称矩阵,存在n阶正交矩阵V,使得ATA相似于对角矩阵STS(对角线上是ATA的全部特征值)。相似的矩阵有相同的特征多项式,进而有相同的特征值,当然秩更要相同了。所以r(S)=r(STS)=r(ATA)=r(A)。即对角阵S非零奇异值的个数=ATA非零特征值的个数=对称矩阵ATA的秩=A的秩。
2.2.2 推论
好了我们可以总结下了,对于任意实矩阵A的奇异值分解,它的右奇异向量(V的列向量)是ATA的特征向量,它的左奇异向量(U的列向量)是AAT的特征向量,而奇异值是这两个对称矩阵相同的非零特征值的平方根(实际上它们两个非零特征值一模一样)。
SVD分解只告诉我们总是存在这样一个分解,并没有说这个分解是唯一的。很显然:特征值次序就可以不一样,显然SVD分解不唯一。但是我们常常把奇异值按照从大到小的顺序排列,这样S就可以由A唯一确定了。[7]和[8]告诉了我们SVD分解什么情况下是唯一的,感兴趣可以看看。
那什么时候SVD分解和特征值分解相等呢?
[10]里面给出了一种说法:2.3 SVD的另一种形式
实矩阵A的奇异值分解A=USVT可以表示为:
其中k=rank(A),即矩阵A的秩。参照2.2我们知道k=rank(AAT)=rank(ATA)=rank(A),这些奇异值和这两个对称矩阵的相同特征值是一一对应关系(平方根),显然k<=min(m,n)。
使用矩阵的分块乘法,得:
后面一项是0,所以可以化为:
如果我们令X为mxk的矩阵,Y为kxn的矩阵:
那么A可以表示为:我们把它展开为向量的外积形式,这就是SVD的另一种表达形式:
那么向量x左乘矩阵A是什么呢?我们看看:
viTx是个标量,所以有:
此时Ax已经表示成了ui的线性组合,每一项线性系数是viTx和σi的乘积,我们知道viTx是x在V坐标系下vi轴上的坐标。结论呼之欲出:在A的作用下,x由n维空间转化到了m维空间中。下一章我们将从空间几何的角度对这个转化进行理解。
3. 几何角度理解奇异值与奇异向量
3.1 从坐标变换理解
3.1.1 从例子到一般
我直接复制[9]中的一个例子过来,作者是西电的张剑湖大佬:
《利用SVD进行推荐(1)矩阵相乘的本质》一文中提到过,向量左乘正交矩阵可以达到将向量旋转的效果。我们还看了一个2阶非对称方阵的实例,它的奇异值变换就是对向量进行旋转-缩放-旋转的过程。当时并没有讲维度变化这个细节。
我们对更一般的形式进行分析:从奇异值分解的角度出发,Ax=USVTx,VTx就是x在V每个列向量所确定的轴进行投影,是先将x映射到V坐标系中(此时x维度和V确定的空间维度相同,也可以理解为旋转x),然后缩放的同时将维度映射到U-1的维度,最后映射到U-1坐标系中(此时SVTx和U-1坐标系维度相同,可以理解为旋转)。
3.1.2 两个问题
第一个问题是,为什么不是在U-1中进行长度为σi的伸缩,而在U-1坐标系中向量的模长却为σi呢?
是这样的,拿v1举例吧,它太过特殊,在V坐标系中的投影坐标是(1,0,…,0)T。而Σ不仅把这个n维的进行了扩维,将n维的(1,0,…,0)T变为m维的(1,0,…,0),同时还进行了第一维度上长度为σ1的伸缩成为了(σ1,0,…,0)。
所以,在投影到U-1坐标系之前,v1已经转化成一个m空间的向量,它的模长就是σ1。而这个m维空间无论用哪组单位正交基来表示,只不过相当于对向量进行旋转换了方向,向量本身的模是不变的。
第二个问题是,如果如问题1所述,那为什么投影到U-1坐标系中,坐标值恰好与U中的基向量是对应的?
实际上在代数上就是这样没有为什么。从几何角度,我们还是在二维中进行分析吧。假设B点逆时针旋转θ度即为A点,顺时针θ度为C点。x1,y1坐标系和x2,y2坐标系就是U和U-1。现在对于B(σ1,0),我们要向x2,y2坐标系中投影,由其相对关系可知,其投影坐标值其实就相当于A点在x,y坐标系中的投影坐标值,也就是(cosθ,sinθ)T*σ1。
发现了吧,当v1乘以对角阵S维度扩展到m时,此时它的坐标是有一个默认的坐标系的,就如下图中的x,y坐标系。而U和U-1空间也如下图中关系所示,它们使用默认坐标系中的坐标来表示自己。在默认坐标系下x和y轴向的伸缩变换在x2,y2中的表示,就如同x1,y1坐标轴向的伸缩变换在x中的表示,当然使用x1,y1坐标轴的基向量的表示啊。
我们可以发现,对于x,y坐标系中的向量OB(σ1,0),无论是逆时针转到了坐标系x1,y1中变为(cosθ,sinθ)T*σ1,还是转到x2,y2坐标系中成为(cosθ,-sinθ)T*σ1,它的模是不变的。这与问题一是呼应的。
3.2 形变的角度理解奇异值
在[2]中,马同学从翻绳游戏开始,对奇异值进行了生动形象的分析,[6]中7.4节也有形变的分析,还有相关例题。感兴趣的可以看一看。
4. 奇异值的最好解读
在知乎问题"奇异值的物理意义是什么?"下,看到一位大牛对奇异值的解读[12],个人认为是对奇异值的一种最好的解读。感谢知乎用户“老鸡蛋”。
5. 特征值分解和奇异值分解区别
适用条件
特征值分解必须是可对角化矩阵(所以必须是方阵。n阶方阵可对角化的定义是相似于一个对角矩阵,充要条件是A有n个线性无关的特征向量[11]),奇异值分解则适用于任意矩阵。特征值/奇异值个数
特征值个数与矩阵的秩没有必然关系,n阶实对称矩阵的非零特征值个数等于矩阵的秩;非零奇异值个数等于矩阵的秩。几何意义
关于几何意义之前讲的比较多,内容较多本文就不再赘述。[10]中对于奇异值分解的几何意义给出了一个很直观的讲法:
6. 奇异值分解在PCA中的应用
在"利用SVD进行推荐(2)特征值与特征向量的直观理解"中我们讲过,对于样本A,PCA的计算过程就是计算协方差矩阵AAT,然后求前k个最大特征值对应的特征向量得到投影矩阵,从而达到降维的目的。当样本非常多的时候,计算协方差矩阵,还要进行特征值分解,这个计算量挺大的。
我们发现SVD分解A=USVT中,左奇异向量ui不就是AAT的特征向量吗?那我们就可以利用SVD分解来计算投影矩阵了。
[13]中Pinard大神说,有些SVD分解算法可以不用求ATA而直接得到A的右奇异矩阵V,也就是可以直接得到U(AT的右奇异矩阵是UT),那这就很nice了。
参考文献
[1] http://www.ams.org/publicoutreach/feature-column/fcarc-svd
[2] https://www.matongxue.com/madocs/306.html[3] http://www-users.math.umn.edu/~lerman/math5467/svd.pdf[4] 张绍飞. 矩阵论教程.第2版[M]. 2012.[5]https://blog.csdn.net/zhongkejingwang/article/details/43053513[6] Lay D , Lay. 线性代数及其应用[M]. 机械工业出版社, 2017.[7] http://rakaposhi.eas.asu.edu/s10-cse494-mailarchive/msg00030.html[8] https://math.stackexchange.com/questions/644327/how-unique-are-u-and-v-in-the-singular-value-decomposition[9] https://wenku.baidu.com/view/389fabcebceb19e8b8f6ba97.html[10] https://www.zhihu.com/question/49959130[11] 申亚男, 张晓丹, 李为东. 线性代数.第2版[M]. 机械工业出版社, 2015.[12] https://www.zhihu.com/question/22237507[13] https://www.cnblogs.com/pinard/p/6251584.html
广告
所有传统推荐算法的代码在:https://github.com/wyl6/Traditional-Classical-Conventional-Recommender-Systems
转载地址:https://blog.csdn.net/weixin_39926014/article/details/111129684 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!