奇异值分解(SVD)的原理详解及推导
1. 写在前面
最近整理推荐系统模型的时候， 第二个模型打算整理一下隐语义模型， 这里面绕不开一种思想就是矩阵分解， 而作为矩阵分解的经典方法SVD感觉这次有必要学学了， SVD不仅是一个数学问题，在工程应用中的很多地方都有它的身影，比如我之前在【白话机器学习篇】说到了PCA， 那是一种经典的降维方式， 而SVD同样的也可以用于降维， 并且掌握了SVD原理后再去看PCA那是相当简单的，在推荐系统方面，SVD更是名声大噪，在2006年， Koren将它应用于推荐系统并获得了Netflix大奖， 因此在推荐系统中也就出来了隐语义模型(Latent Factor Model)或者叫矩阵分解模型(Matrix Fatcorization)， 它们的核心思想是通过寻找隐含特征来联系用户兴趣和商品，说白了其实就是把协同过滤里面的共现矩阵分解成了两个矩阵相乘的方式。 这个在具体整理的时候再谈， 总之， 这里面绕不开的一个名词就是SVD， 尽管数学上的这种SVD矩阵分解由于它对矩阵稠密的要求和计算复杂度大不太直接用于协同过滤里面的共现矩阵，但是源思想没变， 所以在这里先整理一下SVD的原理， 防止在整理矩阵分解模型的时候遇到SVD， RSVD， ASVD， SVD++等各种名词的时候一脸懵逼哈哈。
定理和推论
定理：设A为m*n阶复矩阵，则存在m阶酉阵U和n阶酉阵V，使得：
A = U*S*V’
其中S=diag(σi,σ2,……,σr)，σi>0 (i=1,…,r)，r=rank(A)。
推论：
设A为m*n阶实矩阵，则存在m阶正交阵U和n阶正交阵V，使得
A = U*S*V’
其中S=diag(σi,σ2,……,σr)，σi>0 (i=1,…,r)，r=rank(A)。
说明：
1、 奇异值分解非常有用，对于矩阵A(m*n)，存在U(m*m)，V(n*n)，S(m*n)，满足A = U*S*V’。U和V中分别是A的奇异向量，而S是A的奇异值。AA'的正交单位特征向量组成U，特征值组成S'S，A'A的正交单位特征向量组成V，特征值（与AA'相同）组成SS'。因此，奇异值分解和特征值问题紧密联系。
2、奇异值分解提供了一些关于A的信息，例如非零奇异值的数目（S的阶数）和A的秩相同，一旦秩r确定，那么U的前r列构成了A的列向量空间的正交基。
正交矩阵
正交矩阵是实数特殊化的酉矩阵，因此总是正规矩阵。尽管我们在这里只考虑实数矩阵，
这个定义可用于其元素来自任何域的矩阵。正交矩阵毕竟是从内积自然引出的，对于复
数的矩阵这导致了归一要求。注意正交矩阵的定义：n阶‘实矩阵’ A称为正交矩阵，如果：A×A′=E（E为单位矩阵，
A'表示“矩阵A的转置矩阵”。） 若A为正交阵，则下列诸条件是等价的:
1) A 是正交矩阵
2) A×A′=E（E为单位矩阵）
3) A′是正交矩阵
4) A的各行是单位向量且两两正交
5) A的各列是单位向量且两两正交
6) (Ax,Ay)=(x,y) x,y∈R
这篇文章是基本看着一篇博客整理过来的， 只是对里面的错别字和公式进行了改版， 对里面说的不太清晰的地方简单的补充了一下， 所以并不是完全原创文章， 注明一下原文章出处：https://blog.csdn.net/zhongkejingwang/article/details/43053513， 下面就是这个链接的原文了。
用SVD可以很容易得到任意矩阵的满秩分解，用满秩分解可以对数据做压缩。可以用SVD来证明对任意 M × N M\times N M×N的矩阵均存在如下分解：
这个可以应用在数据降维压缩上！在数据相关性特别大的情况下存储X和Y矩阵比存储A矩阵占用空间更小！在开始讲解SVD之前，先补充一点矩阵代数的相关知识。
2. 正交矩阵
正交矩阵是在欧几里得空间里的叫法，在酉空间里叫酉矩阵，一个正交矩阵对应的变换叫正交变换，这个变换的特点是不改变向量的尺寸和向量间的夹角，那么它到底是个什么样的变换呢？看下面这张图
假设二维空间中的一个向量OA，它在标准坐标系也即e1、e2表示的坐标是中表示为(a,b)’（用’表示转置），现在把它用另一组坐标e1’、e2’表示为(a’,b’)’，存在矩阵U使得(a’,b’)’=U(a,b)’，则U即为正交矩阵。
从图中可以看到，正交变换只是将变换向量用另一组正交基表示，在这个过程中并没有对向量做拉伸，也不改变向量的空间位置，假如对两个向量同时做正交变换，那么变换前后这两个向量的夹角显然不会改变。上面的例子只是正交变换的一个方面，即旋转变换，可以把e1’、e2’坐标系看做是e1、e2坐标系经过旋转某个θ角度得到，怎么样得到该旋转矩阵U呢？假如 x = [ a b ] \mathbf{x}=\left[
abab
\right] x=[ab]， 则：
a ′ = x ⋅ e 1 ′ = e 1 ′ T x b ′ = x ⋅ e 2 ′ = e 2 ′ T x
a′=x⋅e1′=e1′Txb′=x⋅e2′=e2′Txa′=x⋅e1′=e1′Txb′=x⋅e2′=e2′Tx
a′=x⋅e1′=e1′Txb′=x⋅e2′=e2′Tx
a ′ a' a′和 b ′ b' b′实际上是 x \mathbf{x} x在 e 1 ′ e1' e1′和 e 2 ′ e2' e2′轴上的投影大小，所以直接做内积可得，then
[ a ′ b ′ ] = [ e 1 ′ T e 2 ′ T ] x \left[
a′b′a′b′
\right]=\left[
e1′Te2′Te1′Te2′T
\right] \mathbf{x} [a′b′]=[e1′Te2′T]x
从图中可以看到， e 1 e1 e1和 e 2 e2 e2是一组基， 坐标是(1,0), (0,1)， 把这俩投影到新的轴上得到 e 1 ′ e1' e1′和 e 2 ′ e2' e2′， 其实
e 1 ′ = [ ∣ e 1 ∣ cos θ ∣ e 1 ∣ sin θ ] e 2 ′ = [ − ∣ e 1 ∣ sin θ ∣ e 1 ∣ cos θ ] e 1^{\prime}=\left[
|e1|cosθ|e1|sinθ|e1|cosθ|e1|sinθ
\right] \quad e 2^{\prime}=\left[
−|e1|sinθ|e1|cosθ−|e1|sinθ|e1|cosθ
\right] e1′=[∣e1∣cosθ∣e1∣sinθ]e2′=[−∣e1∣sinθ∣e1∣cosθ]
所以
U = [ cos θ sin θ − sin θ cos θ ] \mathbf{U}=\left[
cosθ−sinθsinθcosθcosθsinθ−sinθcosθ
\right] U=[cosθ−sinθsinθcosθ]
正交阵U行（列）向量之间都是单位正交向量。上面求得的是一个旋转矩阵，它对向量做旋转变换！也许你会有疑问：刚才不是说向量空间位置不变吗？怎么现在又说它被旋转了？对的，这两个并没有冲突，说空间位置不变是绝对的，但是坐标是相对的，假如你站在e1上看OA，随着e1旋转到e1’，看OA的位置就会改变。如下图：
如图，如果我选择了e1’、e2’作为新的标准坐标系，那么在新坐标系中OA（原标准坐标系的表示）就变成了OA’，这样看来就好像坐标系不动，把OA往顺时针方向旋转了“θ”角度，这个操作实现起来很简单：将变换后的向量坐标仍然表示在当前坐标系中。
旋转变换是正交变换的一个方面，这个挺有用的，比如在开发中需要实现某种旋转效果，直接可以用旋转变换实现。正交变换的另一个方面是反射变换，也即e1’的方向与图中方向相反，这个不再讨论。
总结：正交矩阵的行（列）向量都是两两正交的单位向量，正交矩阵对应的变换为正交变换，它有两种表现：旋转和反射。正交矩阵将标准正交基映射为标准正交基（即图中从e1、e2到e1’、e2’）
3. 特征值分解—EVD
在讨论SVD之前先讨论矩阵的特征值分解（EVD），在这里，选择一种特殊的矩阵——对称阵（酉空间中叫hermite矩阵即厄米阵）。对称阵有一个很优美的性质：它总能相似对角化，对称阵不同特征值对应的特征向量两两正交。一个矩阵能相似对角化即说明其特征子空间即为其列空间，若不能对角化则其特征子空间为列空间的子空间。现在假设存在mxm的满秩对称矩阵A，它有m个不同的特征值，设特征值为 λ i \lambda_i λi, 对应的特征向量 x i x_i xi， 则有
进而
所以可得到A的特征值分解（由于对称阵特征向量两两正交，所以U为正交阵，正交阵的逆矩阵等于其转置）
这里假设A有m个不同的特征值，实际上，只要A是对称阵其均有如上分解。
矩阵A分解了，相应的，其对应的映射也分解为三个映射。现在假设有x向量，用Ａ将其变换到Ａ的列空间中，那么首先由U’先对x做变换：
A x = U Λ U T x \mathrm{Ax}=U \Lambda U^{T} \mathrm{x} Ax=UΛUTx
U是正交阵 U T U^T UT也是正交阵，所以 U T U^T UT对x的变换是正交变换，它将x用新的坐标系来表示，这个坐标系就是A的所有正交的特征向量构成的坐标系。假如将x用A的所有特征向量表示为：
x = a 1 x 1 + a 2 x 2 + ⋯ + a m x m \mathrm{x}=a_{1} \mathrm{x}_{1}+a_{2} \mathrm{x}_{2}+\cdots+a_{m} \mathrm{x}_{m} x=a1x1+a2x2+⋯+amxm
这个假设是向量x原来的坐标， 那么， 经过第一个变换之后， 就可以把向量x变成[a1, a2, …am]’。
紧接着，在新的坐标系表示下，由中间那个对角矩阵对新的向量坐标换，其结果就是将向量往各个轴方向拉伸或压缩：
从上图可以看到，如果A不是满秩的话，那么就是说对角阵的对角线上元素存在0，这时候就会导致维度退化， 这样就可以降维了看没看到，这样就会使映射后的向量落入m维空间的子空间中。
最后一个变换就是U对拉伸或压缩后的向量做变换，由于U和U’是互为逆矩阵，所以U变换是U’变换的逆变换。
因此，从对称阵的分解对应的映射分解来分析一个矩阵的变换特点是非常直观的。假设对称阵特征值全为1那么显然它就是单位阵，如果对称阵的特征值有个别是0其他全是1，那么它就是一个正交投影矩阵，它将m维向量投影到它的列空间中。
根据对称阵A的特征向量，如果A是2*2的，那么就可以在二维平面中找到这样一个矩形，是的这个矩形经过A变换后还是矩形：
这个矩形的选择就是让其边都落在A的特征向量方向上，如果选择其他矩形的话变换后的图形就不是矩形了！
3. 奇异值分解—SVD
上面的特征值分解的A矩阵是对称阵，根据EVD可以找到一个（超）矩形使得变换后还是（超）矩形，也即A可以将一组正交基映射到另一组正交基！这个意思其实就是上面向量x的那三次变换， 开始的正交基假设的是A个特征向量。 而A变换之后， 又变回到了那组正交基上， 只不过是长度上发生了拉伸或者压缩， 方向没变。可以看那两个矩形。
那么现在来分析：对任意M*N的矩阵，能否找到一组正交基使得经过它变换后还是正交基？答案是肯定的，它就是SVD分解的精髓所在。SVD想做的这个变化不限于是上面的m*m的满秩对称矩阵A， 而是任意的A矩阵。
现在假设存在M*N矩阵A，事实上，A矩阵将n维空间中的向量映射到k（k<=m）维空间中， k=Rank(A)。现在的目标就是：在n维空间中找一组正交基，使得经过A变换后还是正交的。假设已经找到这样一组正交基：
即这组基经过A的变化之后依然是正交的， 则A矩阵将这组基映射为：
如果要使他们两两正交，即
这个地方第一个等式是点乘， 后面是矩阵乘法哈，所以才多出了个转置，不要弄混。 根据前面假设， v i {v_i} vi是一组正交基， 则存在
所以如果正交基v选择为A’A的特征向量的话，即 ( A T A ) v i = λ i v i \left(A^{T} A\right) v_{i}=\lambda_{i} v_{i} (ATA)vi=λivi， 由于A’A是对称阵，v之间两两正交，那么
这样就找到了正交基使其映射后还是正交基了，现在，将映射后的正交基单位化：
因为
这个是上面的 j j j换成 i i i， v i v_i vi是基， 向量表示的时候是某个方向为1， 其他方向是0， 所以自己和自己点乘的结果是1.
所以有
所以取单位向量， 也就是 A v i Av_i Avi单位化
由此可得
当 k < i < = m k < i <= m k<i<=m时，对 u 1 ， u 2 ， . . . ， u k u_1，u_2，...，u_k u1，u2，...，uk进行扩展 u ( k + 1 ) , . . . , u m u_{(k+1)},...,u_m u(k+1),...,um，使得 u 1 ， u 2 ， . . . ， u m u_1，u_2，...，u_m u1，u2，...，um为m维空间中的一组正交基, 同样的，对 v 1 ， v 2 ， . . . ， v k v_1，v_2，...，v_k v1，v2，...，vk进行扩展v_{(k+1)},…,v_n（这n-k个向量存在于A的零空间中，即Ax=0的解空间的基），使得 v 1 ， v 2 ， . . . ， v n v_1，v_2，...，v_n v1，v2，...，vn为n维空间中的一组正交基, 则可得到：
继而可以得到A矩阵的奇异值分解：
正交矩阵转置等于逆。
现在可以来对A矩阵的映射过程进行分析了：如果在n维空间中找到一个（超）矩形，其边都落在A’A的特征向量的方向上，那么经过A变换后的形状仍然为（超）矩形！
v i v_i vi为A’A的特征向量，称为A的右奇异向量， u i = A v i u_i=Av_i ui=Avi实际上为AA’的特征向量，称为A的左奇异向量。下面利用SVD证明文章一开始的满秩分解：
利用矩阵分开乘法展开得：
可以看到第二项为0，有
令
则A=XY即是A的满秩分解。
4.SVD分解
矩阵的奇异值分解（SVD）在最优化问题、特征值问题、最小二乘问题及广义逆问题中有巨大作用，奇异值分解将QR分解推广到任意的实矩阵，不要求矩阵式可逆，也不要求是方阵。奇异值和特征值相似的重要意义，都是为了提取出矩阵的主要特征。假设A是一个m∗n阶矩阵，如此则存在一个分解m阶正交矩阵U、非负对角阵Σ和n阶正交矩阵V使得
A=UΣVT
Σ对角线上的元素Σi,i即为A的奇异值。而且一般来说，我们会将Σ上的值按从大到小的顺序排列。
通过上面对SVD的简单描述，不难发现，SVD解决了特征值分解中只能针对方阵而没法对更一般矩阵进行分解的问题。所以在实际中，SVD的应用场景比特征值分解更为通用与广泛。将将上面的SVD分解用一个图形象表示如下。
截止到这里为止，很多同学会有疑问了：你这不吃饱了撑得。好好的一个矩阵A，你这为毛要将他表示成三个矩阵。这三个矩阵的规模，一点也不比原来矩阵的规模小好么。而且还要做两次矩阵的乘法。要知道，矩阵乘法可是个复杂度为O(n3)的运算。如果按照之前那种方式分解，肯定是没有任何好处的。矩阵规模大了，还要做乘法运算。关键是奇异值有个牛逼的性质：在大部分情况下，当我们把矩阵Σ里的奇异值按从大到小的顺序呢排列以后，很容易就会发现，奇异值σ减小的速度特别快。在很多时候，前10%甚至前1%的奇异值的和就占了全部奇异值和的99%以上。换句话说，大部分奇异值都很小，基本没什么卵用。。。既然这样，那我们就可以用前面r个奇异值来对这个矩阵做近似。于是，SVD也可以这么写：
Am×n≈Um×rΣr×rVr×n
其中，r≪m，r≪n。如果用另外一幅图描述这个过程，如下图：
看了上面这幅图，同学们是不是就恍然大悟：原来的那个大矩阵A，原来可以用右边的那三个小矩阵来表示。当然如果r越大，跟原来的矩阵相似度就越高。如果r=n，那得到的就是原来的矩阵A。但是这样存储与计算的成本就越高。所以，实际在使用SVD的时候，需要我们根据不同的业务场景与需求还有资源情况，合理选择r的大小。本质而言，就是在计算精度与空间时间成本之间做个折中。
SVD分解意义
按照前面给出的几何含义，SVD 分解可以看成先旋转，然后进行分别缩放，然后再旋转的过程。
SVD分解解满秩（亏秩）最小二乘问题
SVD分解不仅可以解决满秩最小二乘问题，最重要的是可以解决亏秩最小二乘问题（r（A）< n，理解下其实就相当于这里取r < n的情况），而前面的方法在秩亏的时候都会失效。
设A的SVD分解为：
参考：