SVD and PCA

SVD

SVD(singular value decomposition,奇异值分解)是一种非常实用的矩阵分解方式，在各种地方频繁遇到SVD和相关的算法却搞不清它到底是什么原理后，我决定深入了解一下。

SVD的几何意义

学过线性代数的人都知道（也可能不知道），矩阵在几何上可以看作对空间的线性变换，比如矩阵$M=\begin{bmatrix} 1 & 0 \\ 2 & 3 \end{bmatrix}$M=[12​03​]对空间所作的线性变换如下图所示：

可以看出，M将原空间的基向量i，j变换为新的基向量（分别为[1,2],[3,0])，对原空间中任意向量，假设为向量v=[1,1],在M转换后Mv=[1,5],也正是以新的基向量$i^{'},j^{'}$i′,j′表示的[1,1]向量。
但是这样描述一个矩阵对空间的变换也太麻烦太抽象了，有没有简单一点的描述方法，比如说用直观的旋转、拉伸这样的方法来描述呢？答案是：有，辣就是，SVD，锵锵~！
为了能够使用这样的直观描述，我们必须找到一组空间的在经受M变换后仍然是正交的正交基向量：

好消息是，数学家告诉我们对于任何一个矩阵M，这样的正交基向量都存在。这个结论此处不予证明，请拿出对数学的信仰。（开玩笑啦，如感兴趣可以搜索SVD证明。）
现在假设我们找到了这样的一组基向量$[v_1,v_2]$[v1​,v2​](此处以二维空间为例)，经过矩阵M变换后成为$[Mv_1,Mv_2]$[Mv1​,Mv2​]。根据前面所说的性质可知，$[Mv_1,Mv_2]$[Mv1​,Mv2​]仍然是正交向量。

我们将$[Mv_1,Mv_2]$[Mv1​,Mv2​]方向的单位向量表示为$[u_1,u_2]$[u1​,u2​],那么$[Mv_1,Mv_2]$[Mv1​,Mv2​]可以表示为$[\sigma_1 u_1,\sigma_1 u_2]$[σ1​u1​,σ1​u2​]。

请注意，因为$[v_1,v_2]$[v1​,v2​]和$[u_1,u_2]$[u1​,u2​]都是空间的正交基，因此它们所代表的线性变换为单纯的旋转变换，并且其逆矩阵等于其转置矩阵。（线性代数基础，如果不记得的话就继续靠对数学的信仰吧~）
此时对于任意一个向量x，我们可以将其表示为如下形式：
$x = [v_1,v_2][v_1^T,v_2^T]x$x=[v1​,v2​][v1T​,v2T​]x
（$[v_1,v_2][v_1^T,v_2^T]$[v1​,v2​][v1T​,v2T​]两者相乘的结果是相互抵消，等于标准正交基 $I$I，也就是等于没变）
对x做矩阵M变换：
$\begin{aligned} Mx &= M[v_1,v_2][v_1^T,v_2^T]x \\ &= [\sigma_1 u_1,\sigma_1 u_2][v_1^T,v_2^T]x \\ &= [u_1,u_2]\begin{bmatrix} \sigma_1 & 0 \\ 0 & \sigma_1 \end{bmatrix}[v_1^T,v_2^T]x \end{aligned}$Mx​=M[v1​,v2​][v1T​,v2T​]x=[σ1​u1​,σ1​u2​][v1T​,v2T​]x=[u1​,u2​][σ1​0​0σ1​​][v1T​,v2T​]x​
将上式整理为矩阵形式并消去x，则得到：
$M = U\Sigma V^T$M=UΣVT

锵锵~！我们得到了矩阵的奇异值分解~！
有人可能会说了，这把一个矩阵分解成三个矩阵难道不是更复杂了吗？但是U和$V^T$VT都是正交矩阵，对应于旋转操作，而$\Sigma$Σ是对角矩阵，对应于拉伸操作，那么经过这样的分解后，任意一个矩阵都可以分解为旋转-拉伸-旋转三次简单操作的组合，在几何理解上更加直观。

SVD的计算

接下来我们来看一看怎样计算得到这三个矩阵,首先把$MM^T$MMT相乘，看看会发生什么：
$\begin{aligned} MM^{T} &= U\Sigma V^T[U\Sigma V^T]^T \\ &= U\Sigma V^TV\Sigma U^T \\ &= U\Sigma ^2 U^T \end{aligned}$MMT​=UΣVT[UΣVT]T=UΣVTVΣUT=UΣ2UT​
$\begin{aligned} M^{T}M &= [U\Sigma V^T]^TU\Sigma V^T \\ &= V\Sigma U^TU\Sigma V^T \\ &= V\Sigma ^2 V^T \end{aligned}$MTM​=[UΣVT]TUΣVT=VΣUTUΣVT=VΣ2VT​
是不是有点眼熟？没错~！这就是特征值分解，那么怎样计算$U,V,和\Sigma$U,V,和Σ也就很清楚了：

1. 计算 $MM^{T}$MMT 和 $M^{T}M$MTM；
2. 分别计算 $MM^{T}$MMT 和 $M^{T}M$MTM 的特征向量及其特征值；
3. $MM^{T}$MMT 的特征向量组成 U；而 $M^{T}M$MTM 的特征向量组成 V；
4. 对 $MM^{T}$MMT 和 $M^{T}M$MTM 的非零特征值求平方根，对应上述特征向量的位置，填入 Σ 的对角元。

另外值得一提的是特征值分解和奇异值分解之间本身就存在这非常多的联系，如果不那么精确地说，奇异值分解可以算是特征值分解的非方正补丁加强版。特征值分解只能分解方阵，而奇异值分解适用于各种形状的矩阵，因此在实际应用上更方便。但是从思想和用途上，两者其实非常相似。

SVD的应用

SVD除了为矩阵变换提供了一个更直观的几何理解，还有很多其他的应用。这里主要讲一讲基于SVD的PCA降维。PCA的目的是将一个矩阵A(nxd)变换为维度较低的矩阵B(nxk)的同时使数据的方差最大，协方差最小。
说到方差和协方差，那么肯定要提到协方差矩阵$A^TA$ATA(这里为了描述方便认为A已经均值归零)。如果你不记得了的话：协方差矩阵$A^TA$ATA的对角线元素为A的方差，除对角线以外元素为协方差。
那么我们可以重新表述PCA的目的为：将一个矩阵A(nxd)变换为维度较低的矩阵B(nxk)，使得$B^TB$BTB的对角线元素最大，其他元素最小。
$A^TA$ATA是一个实对称矩阵，因此可以做特征值分解：
$A^TA = V\Sigma V^T$ATA=VΣVT
It turns out，矩阵A在其特征值最大的特征向量的方向上的投影既是方差最大的投影，并且其投影的方差就等于对于的特征值。所以，
$B=AV$B=AV
这里不具体证明上述结论（主要是我也不知道怎么证明），但是我们可以计算矩阵B的协方差矩阵验证一下：
$\begin{aligned} B^TB &= V^TA^TAV \\ &= V^TV\Sigma V^TV \\ &= \Sigma \end{aligned}$BTB​=VTATAV=VTVΣVTV=Σ​
$\Sigma$Σ为对角矩阵，其对角线元素为特征值，其余均为0，符号我们上面所说的“使得$B^TB$BTB的对角线元素最大，其他元素最小”的要求。
但是特征值分解需要计算$A^TA$ATA,是一个比较费时的过程，有没有更高效的算法呢？
这里就是SVD入场的时候了！因为SVD并不挑剔矩阵的形状，因此矩阵A可以进行奇异值分解：
$A = U\Sigma V^T$A=UΣVT
而这里的V和上面的$B=AV$B=AV是同一个矩阵。为什么呢？请回忆一下奇异值分解的计算中，矩阵V是怎么的来的来着？正是协方差矩阵$A^{T}A$ATA 的特征向量组成了V！所以：
$\begin{aligned} B &= AV \\ &= U\Sigma V^TV \\ &= U\Sigma \end{aligned}$B​=AV=UΣVTV=UΣ​
不用计算协方差矩阵！也不用计算协方差矩阵的特征值分解！只需直接计算矩阵A的SVD! PCA降维矩阵B直接带回家！

当然，除了PCA，SVD在其他很多方面都有应用，这里不再列举。