某某机械设备有限公司欢迎您!

奇异值分解(SVD)原理详解及推导

时间:2020-03-15

  在网上看到有很多文章介绍SVD的,讲的也都不错,但是感觉还是有需要补充的,特别是关于矩阵和映射之间的对应关系。前段时间看了国外的一篇文章,叫A Singularly Valuable Decomposition The SVD of a Matrix,觉得分析的特别好,把矩阵和空间关系对应了起来。本文就参考了该文并结合矩阵的相关知识把SVD原理梳理一下。

  SVD不仅是一个数学问题,在工程应用中的很多地方都有它的身影,比如前面讲的PCA,掌握了SVD原理后再去看PCA那是相当简单的,在推荐系统方面,SVD更是名声大噪,将它应用于推荐系统的是Netflix大奖的获得者Koren,可以在Google上找到他写的文章;用SVD可以很容易得到任意矩阵的满秩分解,用满秩分解可以对数据做压缩。可以用SVD来证明对任意M*N的矩阵均存在如下分解:

  这个可以应用在数据降维压缩上!在数据相关性特别大的情况下存储X和Y矩阵比存储A矩阵占用空间更小!

  正交矩阵是在欧几里得空间里的叫法,在酉空间里叫酉矩阵,一个正交矩阵对应的变换叫正交变换,这个变换的特点是不改变向量的尺寸和向量间的夹角,那么它到底是个什么样的变换呢?看下面这张图

  假设二维空间中的一个向量OA,它在标准坐标系也即e1、e2表示的坐标是中表示为(a,b)(用表示转置),现在把它用另一组坐标e1、e2表示为(a,b),存在矩阵U使得(a,b)=U(a,b),则U即为正交矩阵。从图中可以看到,正交变换只是将变换向量用另一组正交基表示,在这个过程中并没有对向量做拉伸,也不改变向量的空间位置,加入对两个向量同时做正交变换,那么变换前后这两个向量的夹角显然不会改变。上面的例子只是正交变换的一个方面,即旋转变换,可以把e1、e2坐标系看做是e1、e2坐标系经过旋转某个斯塔角度得到,怎么样得到该旋转矩阵U呢?如下

  a和b实际上是x在e1和e2轴上的投影大小,所以直接做内积可得,then

  正交阵U行(列)向量之间都是单位正交向量。上面求得的是一个旋转矩阵,它对向量做旋转变换!也许你会有疑问:刚才不是说向量空间位置不变吗?怎么现在又说它被旋转了?对的,这两个并没有冲突,说空间位置不变是绝对的,但是坐标是相对的,加入你站在e1上看OA,随着e1旋转到e1,看OA的位置就会改变。如下图:

  如图,如果我选择了e1、e2作为新的标准坐标系,那么在新坐标系中OA(原标准坐标系的表示)就变成了OA,这样看来就好像坐标系不动,把OA往顺时针方向旋转了“斯塔”角度,这个操作实现起来很简单:将变换后的向量坐标仍然表示在当前坐标系中。

  旋转变换是正交变换的一个方面,这个挺有用的,比如在开发中需要实现某种旋转效果,直接可以用旋转变换实现。正交变换的另一个方面是反射变换,也即e1的方向与图中方向相反,这个不再讨论。

  总结:正交矩阵的行(列)向量都是两两正交的单位向量,正交矩阵对应的变换为正交变换,它有两种表现:旋转和反射。正交矩阵将标准正交基映射为标准正交基(即图中从e1、e2到e1、e2)

  在讨论SVD之前先讨论矩阵的特征值分解(EVD),在这里,选择一种特殊的矩阵——对称阵(酉空间中叫hermite矩阵即厄米阵)。对称阵有一个很优美的性质:它总能相似对角化,对称阵不同特征值对应的特征向量两两正交。一个矩阵能相似对角化即说明其特征子空间即为其列空间,若不能对角化则其特征子空间为列空间的子空间。现在假设存在mxm的满秩对称矩阵A,它有m个不同的特征值,设特征值为

  所以可得到A的特征值分解(由于对称阵特征向量两两正交,所以U为正交阵,正交阵的逆矩阵等于其转置)

  矩阵A分解了,相应的,其对应的映射也分解为三个映射。现在假设有x向量,用A将其变换到A的列空间中,那么首先由U先对x做变换:

  U是正交阵U也是正交阵,所以U对x的变换是正交变换,它将x用新的坐标系来表示,这个坐标系就是A的所有正交的特征向量构成的坐标系。比如将x用A的所有特征向量表示为:

  紧接着,在新的坐标系表示下,由中间那个对角矩阵对新的向量坐标换,其结果就是将向量往各个轴方向拉伸或压缩:

  从上图可以看到,如果A不是满秩的话,那么就是说对角阵的对角线,这时候就会导致维度退化,这样就会使映射后的向量落入m维空间的子空间中。

  最后一个变换就是U对拉伸或压缩后的向量做变换,由于U和U是互为逆矩阵,所以U变换是U变换的逆变换。

  因此,从对称阵的分解对应的映射分解来分析一个矩阵的变换特点是非常直观的。假设对称阵特征值全为1那么显然它就是单位阵,如果对称阵的特征值有个别是0其他全是1,那么它就是一个正交投影矩阵,它将m维向量投影到它的列空间中。

  根据对称阵A的特征向量,如果A是2*2的,那么就可以在二维平面中找到这样一个矩形,是的这个矩形经过A变换后还是矩形:

  这个矩形的选择就是让其边都落在A的特征向量方向上,如果选择其他矩形的话变换后的图形就不是矩形了!

  上面的特征值分解的A矩阵是对称阵,根据EVD可以找到一个(超)矩形使得变换后还是(超)矩形,也即A可以将一组正交基映射到另一组正交基!那么现在来分析:对任意M*N的矩阵,能否找到一组正交基使得经过它变换后还是正交基?答案是肯定的,它就是SVD分解的精髓所在。

  现在假设存在M*N矩阵A,事实上,A矩阵将n维空间中的向量映射到k(k=m)维空间中,k=Rank(A)。现在的目标就是:在n维空间中找一组正交基,使得经过A变换后还是正交的。假设已经找到这样一组正交基:

  所以如果正交基v选择为AA的特征向量的话,由于AA是对称阵,v之间两两正交,那么

  这样就找到了正交基使其映射后还是正交基了,现在,将映射后的正交基单位化:

  同样的,对v1,v2,...,vk进行扩展v(k+1),...,vn(这n-k个向量存在于A的零空间中,即Ax=0的解空间的基),使得v1,v2,...,vn为n维空间中的一组正交基,即

  现在可以来对A矩阵的映射过程进行分析了:如果在n维空间中找到一个(超)矩形,其边都落在AA的特征向量的方向上,那么经过A变换后的形状仍然为(超)矩形!

  vi为AA的特征向量,称为A的右奇异向量,ui=Avi实际上为AA的特征向量,称为A的左奇异向量。下面利用SVD证明文章一开始的满秩分解:

  整个SVD的推导过程就是这样,后面会介绍SVD在推荐系统中的具体应用,也就是复现Koren论文中的算法以及其推导过程。

  1.前言第一次接触奇异值分解还是在本科期间,那个时候要用到点对点的刚体配准,这是查文献刚好找到了四元数理论用于配准方法(点对点配准可以利用四元数方法,如果点数不一致更建议应用ICP算法)。一直想找个时...博文来自:沈春旭的博客

  与PCA一样的学习过程,在学习SVD时同样补习了很多的基础知识,现在已经大致知道了PCA的应用原理,SVD个人感觉相对要难一点,但主要步骤还是能勉强理解,所以这里将书本上的知识和个人的理解做一个记录。...博文来自:昆兰.沃斯 的博客

  目录一、特征分解(特征值、特征向量)二、正定、半正定、负定三、奇异值(SVD)分解一、特征分解(特征值、特征向量)许多数学对象可以通过将它们分解成多个组成部分或者找到它们的一些属性以便更好地理解,这些...博文来自:Yancy的博客

  SVD原理以及推导一。关于这篇文章的开始几句话       看过我之前写过文章的童鞋们会发现我写文章的水平很烂的,所以看官们见谅啊!SVD不仅是一个数学问题,在数学问题上主要涉及矩阵的计算,矩阵已经忘...博文来自:PANHUBO的博客

  PCA的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的。特征值和奇异值在大部分人的印象中,往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面,也很少讲任何跟特征值与奇异值...博文来自:的博客

  在数据挖掘或者图像处理等领域经常会用到主成分分析,这样做的好处是使要分析的数据的维度降低了,但是数据的主要信息还能保留下来,并且,这些变换后的维两两不相关!至于为什么?那就接着往下看。在本文中,将会很...博文来自:学无常师,负笈不远险阻

  转载请声明出处在网上看到有很多文章介绍SVD的,讲的也都不错,但是感觉...博文来自:Miracle.Zhao的博客

  前面文章SVD原理及推导已经把SVD的过程讲的很清楚了,本文介绍如何将SVD应用于推荐系统中的评分预测问题。其实也就是复现Koren在NetFlix大赛中的使用到的SVD算法以及其扩展出的RSVD、S...博文来自:学无常师,负笈不远险阻

  版权声明: 本文由LeftNotEasy发布于本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gm...博文来自:weixin_33854644的博客

  当时买mac的初衷,只是想要个固态硬盘的笔记本,用来运行一些复杂的扑克软件。而看了当时所有的SSD笔记本后,最终决定,还是买个好(xiong)看(da)的。已经有好几个朋友问我mba怎么样了,所以今天...博文来自:Diana5253的博客

  此游戏全部由本人自己制作完成。游戏大部分的素材来源于原版游戏素材,少部分搜集于网络,以及自己制作。 此游戏为同人游戏而且仅供学习交流使用,任何人未经授权,不得对本游戏进行更改、盗用等,否则后果自负。目...博文来自:尔灵尔亿的博客

  点击蓝色“Creator星球游戏开发社区”关注我哟加个“星标”,一起快乐成长二哥,你好,我想知道一般程序猿都如何接私活,我也想接,能告诉我一些方法吗?上面是一个读者“烦不烦”问我的一个问题。其实不止是...博文来自:奎特尔星球

  奇异值分解则是特征值分解在任意矩阵上的推广,在信号处理、统计学、机器学习等领域有重要应用。下面一起来了解一下吧!...博文来自:Blogs of zcy1221

  不要再问我python好不好学了我之前做过半年少儿编程老师,一个小学四年级的小孩子都能在我的教学下独立完成python游戏,植物大战僵尸简单版,如果要肯花时间,接下来的网络开发也不是问题,人工智能也可...博文来自:一行数据

  奇异值分解,就是把矩阵分成多个“分力”。奇异值的大小,就是各个“分力”的大小。之前在介绍矩阵特征值与特征向量的时候,也是以运动作为类比。一、通俗理解奇异值1、翻绳对于翻绳的这个花型而言,是由四只手完成...博文来自:的博客

  一、准备工作u盘,电脑一台,win10原版镜像(msdn官网)二、下载wepe工具箱极力推荐微pe(微pe官方下载)下载64位的win10 pe,使用工具箱制作启动U盘打开软件,选择安装到U盘(按照操...博文来自:weixin_41964258的博客

  概述PCA的实现一般有两种,一种是用特征值分解去实现的,一种是用奇异值分解去实现的。特征值和奇异值在大部分人的印象中,往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面,也很少讲任何跟特征值与奇...博文来自:weixin_30599769的博客

  很早就很想写这个,今天终于写完了。游戏截图:编译环境: VS2017游戏需要一些图片,如果有想要的或者对游戏有什么看法的可以加我的 讨论,如果暂时没有回应,可以在博客下方留言...博文来自:张宜强的博客

  昨天,有网友私信我,说去阿里面试,彻底的被打击到了。问了为什么网上大量使用ThreadLocal的源码都会加上private static?他被难住了,因为他从来都没有考虑过这个问题。无独有偶,今天笔...博文来自:web前端学习交流群:600610151

  一、前言在可视化化程序设计的今天,借助于集成开发环境可以很快地生成程序,程序设计不再是计算机专业人员的专利。很多人认为,只要掌握几种开发工具就可以成为编程高手,其实,这是一种误解。要想成为一个专业的开...博文来自:牧小农

  其实,这篇文章,我应该早点写的,毕竟现在已经2月份了。不过一些其它原因,或者是我的惰性、还有一些迷茫的念头,让自己迟迟没有试着写一点东西,记录下,或者说是总结下自己前3年的工作上的经历、学习的过程。 ...博文来自:x763795151的博客

  引言最近也有很多人来向我请教,他们大都是一些刚入门的新手,还不了解这个行业,也不知道从何学起,开始的时候非常迷茫,实在是每天回复很多人也很麻烦,所以在这里统一作个回复吧。Java学习路线当然,这里...博文来自:java_sha的博客

  从 PC 时代至今,众人只知在 CPU、GPU、XPU、制程、工艺等战场中,英特尔在与同行硬件芯片制造商们的竞争中杀出重围,且在不断的成长进化中,成为全球知名的半导体公司。殊不知,在「刚硬」的背后,英...博文来自:CSDN资讯

  杨辉三角 是经典算法,这篇博客对它的算法思想进行了讲解,并有完整的代码实现。...博文来自:扬帆向海的博客

  三四月份投了字节跳动的实习(图形图像岗位),然后hr打电话过来问了一下会不会opengl,c++,shador,当时只会一点c++,其他两个都不会,也就直接被拒了。七月初内推了字节跳动的提前批,因为内...博文来自:ljh_shuai的博客

  文章有点长并且绕,先来个图片缓冲下!前言现在的业务场景越来越复杂,使用的架构也就越来越复杂,分布式、高并发已经是业务要求的常态。像腾讯系的不少服务,还有CDN优化、异地多备份等处理。说到分布式,就必然...博文来自:公众号-[程序员之道]

  从业五年多,辗转两个大厂,出过书,创过业,从技术小白成长为基层管理,联合几个业内大牛回答下这个问题,希望能帮到大家,记得帮我点赞哦。敲黑板!!!读了这篇文章,你将知道如何才能进大厂,如何实现财务自由,...博文来自:启舰

  很遗憾,这个春节注定是刻骨铭心的,新型冠状病毒让每个人的神经都是紧绷的。那些处在武汉的白衣天使们,尤其值得我们的尊敬。而我们这些窝在家里的程序员,能不外出就不外出,就是对社会做出的最大的贡献。有些读者...博文来自:沉默王二

  一、背景二、爬取数据三、数据分析1、总人口2、男女人口比例3、人口城镇化4、人口增长率5、人口老化(抚养比)6、各省人口7、世界人口四、遇到的问题遇到的问题1、数据分页,需要获取从1949-2018年...博文来自:猪哥

  爬虫福利一:27报网MM批量下载 点击看了本文,相信大家对爬虫一定会产生强烈的兴趣,激励自己去学习爬虫,在这里提前祝:大家学有所成!目标网站:妹子图网环境:Python3.x相关第三方模块:requ...博文来自:Nick.Peng 的博客

  :写的真好,主要是介绍了物理意义。最烦光有公式没有物理意义的介绍了,没了物理意义,数学公式还有什么用!

  lx20012002:[reply][/reply]Vi是AA^T的特征向量,U是对V的单位化,才引出的AV=δU,而V是挑选的一组正交基,并通过一步步推导发现,当假设V是AA^T的特 征向量时,满足我们最初的假设条件,即:在n维空间中找一组正交基,使得经过A变换后还是正交的

  lx20012002:楼主真的太牛逼了,整个推导过程清晰明了,而且更透彻的了解了正交阵的是旋转矩阵的几何旋转过程!!!SVD推导也是真的太牛了!!!!服了!!!