奇异值分解（SVD）

一、理论篇

上周说了PCA（主成分分析）的由来和应用，这周要讲SVD（奇异值分解），不免问一句，它们二者有啥区别和联系？

先讲PCA，它是一种统计方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。

PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。

它的核心是怎样让转换后的数据方差最大、协方差最小。

但是有个要命的问题：它对原始矩阵做了(1)零均值化(2)转置相乘，经过这两步，原始数据早已面目全非，不仅不稳定，而且丢失了矩阵的稀疏性和精度

勿忘初心，我们的目的是什么？最大程度上，用最小的空间保留数据最多的信息。

那我们能不能不对矩阵进行零均值化和转置相乘，直接把一个大矩阵拆分成多个小矩阵？

打个比方说吧。假如我们有一张15x25的图像：

如果直接用大矩阵来表示：

看吧，这样多浪费空间！有很多相关的地方，比如第1,2,倒数1,2列，是一样的

那如果我们把张图片相关的部分全部去掉，只留下不相关的呢？只有三列不相关：

我们的目的达到了，没有对原始数据做零均值、转置相乘，直接将大矩阵分为不相关三个小矩阵，用最小的空间保留了原始数据最多的信息。（当然还得再加个维度：大矩阵的第1,2,倒数1,2列为第一个小矩阵……后续会谈到）

总结：PCA给数据降维有较大的局限性，可直接将大矩阵拆分成小矩阵，保留了更多更精确的信息，而同样达到了降维的目的。

那么问题来了，怎么拆？

谈到拆矩阵，最熟悉的当然是特征值分解了。

但这里有个前提，A必须是对称矩阵。（由于对称阵特征向量两两正交，所以U为正交阵，正交阵的逆矩阵等于其转置）

讲到这，又要给自己科普一些矩阵知识了：矩阵变换。

一个二维向量X(你可以想象成一根箭头)，怎样表示它的信息呢？x轴y轴(箭头投影到x轴y轴得到两个数a,b，用这两个数便表示了它全部的信息)。闲的蛋疼（我实在不想解释我为什么闲得蛋疼），我突然用U乘以X，

这个东西，学名叫：正交变换，正交矩阵将标准正交基映射为另一组标准正交基。

X还是那个X，信息还是这点信息，但是表示它的方式变了，我们换了一组正交基来表示。对基来讲，我本来是一组安分守己的好基，x轴y轴，被你的U一乘，再也不如以前那般堂堂正正了。

再回到拆矩阵。假设我们要拆的矩阵A就是那个U，对向量X做变换。

U’(表示U的转置)是正交矩阵，后半部分U’X不就是我们上面讨论的正交变换吗，于是我们可以用新的基来表示X，得到X的新的坐标（注意：X还是这个X，只是在U’这个坐标系下表示罢了），上式右边则可表示为：

其中，a1,a2,…,am，为X的新坐标，在U’这组基(这个坐标系)下的坐标值。再继续往左变换：

这一步变换好理解，就是对X在新坐标下的拉伸。

此时又回到了正交变换，这次是拉伸后的坐标用U变换，而U和U’互为逆矩阵，所以第三次变换和第一次变换互为逆变换。

总结：

一个向量X，被对称矩阵A变换，有三步：

1.A特征向量U’的正交变换

2.A特征值lambda的伸缩变换

3.A特征向量U的正交变换（第1步的逆变换）

站在基的角度，X还是那个X，是基被A变换了，所以对X才有了不同的表示。

因为U和U’都是正交基，所以被A变换前的基是正交基，变换后的基还是正交基。

科普完毕。

上面的分析都是针对对称矩阵，拆的是对称矩阵。再回顾一下我们要做什么：把大矩阵拆成多个不相关的小矩阵。说起不相关，就想到了正交。

于是目的变成了：怎样把大矩阵A拆成小矩阵A1.A2.A3...,而A1,A2,A3…还是正交的。

怎样判断小矩阵是正交的呢？我们想到了，正交矩阵将标准正交基映射为另一组标准正交基

最后，我们的目的就变成了：找到一组正交基，经过矩阵变换后还是正交基

那么，对任意M*N的矩阵，能否找到一组正交基使得经过它变换后还是正交基？能！

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

则A矩阵将这组基映射为：

如果要使他们两两正交，即

因为V为正交矩阵，所以

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

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

因为

所以有

提取单位向量

由此可得

当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矩阵的奇异值分解：

总结：

最后我们把任意一个矩阵A拆分成三部分：

1.V’,A'A的特征向量的转置，表示了原始域的标准正交基

2.U,A.V,表示经过A变换后的co-domain的标准正交基

3.Σ,A'A特征值构成的对角矩阵，表示了V中的向量与U中相对应向量之间的关系

到此，我们便达到了我们的目的：将一个大矩阵拆分成多个不相关（正交）的小矩阵。

二、应用篇

SVD的应用好多，都好叼，现在不会。下回专门一篇文章再说。对SVD的理解还很浅，可能有些地方不知所以然甚至是错的。万一朋友圈有大神一不小心瞄了一眼，还望指点一二。

或有相关书籍、资料推荐的，更是感恩不尽

参考：

http://blog.csdn.net/wangjian1204/article/details/50642732

http://blog.jobbole.com/88208/

http://blog.chinaunix.net/uid-20761674-id-4040274.html

http://blog.csdn.net/zhongkejingwang/article/details/43053513