我理解的SVD





本科学数学的时候就发现,有一些定义、定理确实是需要仔细琢磨的。课本从来不会或者很少会告诉我们为什么需要某个定义,为什么如此定义,为什么要提出这样的定理,这个定理有什么意义。以前偶尔还会自己去思考一下其中的道理,但是慢慢的也变得懒了。最近看到有人转载matrix67的博文,觉得确实有必要重新的审视一下自己学过的东西。
SVD本科的时候就知道,数学建模的时候还曾经用过,但当时完全是照抄论文,自己并不明白其中的道理。现在回过头去看一看,希望能理解的更透彻一些。以下理解都是我个人的看法,难免有误,敬请指正。
所谓SVD(Singular Value Decompositon)中文翻译为奇异值分解,是数值代数中很重要的概念。首先陈述一下传统的定义,这里我们仅考虑实矩阵。
对于任意m×n的矩阵M,存在分解M=U \Sigma V^T,其中U是m×m阶正交矩阵,V是n×n阶正交矩阵。\Sigma是对角矩阵,对角线上的元素成为奇异值。U和V的列向量分别被成为左奇异向量和右奇异向量。
为什么需要这样一个定义,SVD在物体识别中就有应用,可以结合来理解。我有两张照片,照片中都有一本相同的书,一本横着放且照片拍的比较大,一本竖着放且照片拍的比较小。直观上看,第一本书是可以旋转再缩小一下而和第二本书完全重合,这样我们就可以发现两个照片中实际上存在着相同的东西。这种操作实际上可以用一个变换来实现,对于第一本书上的任何一个点(x,y)^T,可以左乘一个矩阵A而得到第二本书上的对应点坐标。这种操作实际上可以分解为首先对(x,y)^T进行旋转,把书“放正”,然后再沿着坐标轴拉伸把它缩小到和第二本书一样大小,再把他旋转到和第二本书重合。所以可以使用SVD便捷的找到相同的物体,具体细节不详细描述。上述三种操作分别对应了矩阵V,矩阵\Sigma,和矩阵U。因为矩阵\Sigma是对角矩阵,因此它只是在做沿着坐标轴方向的拉伸,而正交矩阵所做的就是旋转。
SVD还可以用来干什么呢?其中矩阵\Sigma的对角线上可能有一些非零但是很接近零的元素,这就相当于沿着坐标轴的拉伸基本上把那一维“变没了”。如果我们直接强行把那一维“变没”,似乎也没有多大影响,但是这样做的意义就是原来的变换的维数降低了。数据挖掘中的主成分分析法实际上就是将那些非常接近0的奇异值直接变成0,然后得到的新矩阵的维数就降低了,但是却仍然和原来的矩阵“几乎相同”。新得到的矩阵比原来的矩阵的秩要低,比如原矩阵的秩是n,如果你要得到一个秩为n-1的近似矩阵,SVD基本上是最好的方法,可以证明这样得到的近似矩阵是所有近似矩阵当中和原来矩阵在某种意义上“最接近”的,也即对应元素的差的平方和最小。
推荐系统中也有SVD的存在,假设我估计出了每一个用户对每一个电影的打分,于是有了一个打分矩阵R。我们让每一个用户对应一个K维向量u,每一个电影对应一个K维向量v,以此来表述他们各自的特征,并令u和v的内积为用户对电影的打分。这样实际上打分矩阵就可以表示为UV^T,其中U的每一行代表一个用户对应的向量,V的每一行代表一个物品对应的向量。一般来说K很小,因此UV^T的秩是不超过K的,这样相当于我需要用一个秩为K的矩阵去近似原来的打分矩阵R,按照前面所述,最好的办法就是对R做SVD,然后只保留其前K个最大的奇异值,其余的均变成0即可。
在Matlab中直接有现成的svd函数可以调用,在Lapack中也有svd的相应函数,在Python的scipy包中,也可以找到svd函数。

本文来自Dora Blog,题目为我理解的SVD,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987