奇异值分解SVD

奇异值分解SVD原理

特征值和特征向量

特征值和特征向量表示：

[Ax=lambda x ]

其中A是一个(n imes n)的实对称矩阵，x是一个n维向量，则我们说(lambda)是一个特征值，而x是矩阵A的特征值(lambda)对应的特征向量。有了特征值和特征向量，我们就可以将矩阵分解。假设我们求出了n个特征值(lambda_1lelambda_2le...lelambda_n)以及这n个特征值的特征向量({w_1,w_2,...,w_n})，如果这n个特征向量线性无关，那么A就可以用下式表示

[A=WSigma W^{-1} ]

其中W是这n个特征向量所形成的(n imes n)维矩阵，而(Sigma)为这n个特征值为对角线的(n imes n)维矩阵。

一般我们会所W的这n个特征向量标准化，即满足(lVert w_i Vert_2=1)，或者说(w_i^Tw_i=1)，此时W的n个特征向量为标准正交基，满足(W^TW=I)即(W^T=W^{-1})，也就是说W为酉矩阵。

这样，我们的特征分解表达式可以写为

[A=WSigma W^T ]

此时，A必须为方阵，如果A不是方阵那么就用到了SVD。

SVD定义

SVD进行矩阵分解时不要求矩阵为方阵，假设矩阵A为一个(m imes n)的矩阵，那么定义矩阵A的SVD为：

[A＝USigma V^T ]

其中U是一个(m imes m)的矩阵；(Sigma)是一个(m imes n)的矩阵，除了主对角线外的元素都为0，主对角线上的元素都为奇异值；V是一个(n imes n)的矩阵。U和V都是酉矩阵，即满足(U^TU=I,V^TT=I)。

三个矩阵的求解：

使用A的转置矩阵，假设

[(A^TA)v_i=lambda_iv_i ]

这样(A^TA)是一个方阵，可得到其n个特征值和对应的特征向量(v)，将特征向量组成一个(n imes n)的矩阵，这里就是我们SVD公式里的V矩阵，一般我们将V中的每个特征向量叫做A的右奇异向量。

如果

[（AA^T)u_i=lambda_iu_i ]

得到m个特征值和对应的m个特征向量，组成一个(m imes m)的矩阵，这里就是SVD公式里的U矩阵，一般将U中的特征向量叫做A的左奇异向量。

有了U和V后，只需要再求得(Sigma)只需求出每个奇异值(sigma)即可。

[egin{align} A&=USigma V^T\ Rightarrow AV&=USigma V^TV\ Rightarrow AV&=USigma\ Rightarrow Av_i&=sigma_iu_i\ Rightarrowsigma_i&=frac{Av_i}{u_i} end{align} ]

这样，我们就可以根据(A,v,u)求出所有的奇异值(sigma)，进而得到矩阵(Sigma)。

另一种方法求解，我们说(A^TA)的特征向量矩阵就是我们SVD中的V矩阵，(AA^T)的特征向量组成的矩阵是我们SVD中的U矩阵，如何证明

[egin{align} A&=USigma V^T\ Rightarrow A^T&=VSigma^TU^T\ Rightarrow A^TA&=VSigma^TU^TUSigma V^T\ &=VSigma^2V^T end{align} ]

上式证明用了：(U^TU=I,Sigma^TSigma=Sigma^2)，可以看出(A^TA)的特征向量组成的矩阵确实是SVD中的V矩阵。

进一步，我们可以看出特征值矩阵等于奇异值矩阵的平方，也就是

[sigma_i=sqrtlambda_i ]

我们可以不用(sigma_i=frac{Av_i}{u_i})来算奇异值，可以直接通过求出(A^TA)的特征值，取平方根来找到奇异值。

SVD的性质

奇异值由大到小排列，而且减小特别快，我们可以选择最大的k个奇异值，k比n小的多，这个重要的性质可以用于降维或数据压缩。SVD可以用于PCA降维。

SVD总结

PCA降维时，需要计算协方差矩阵(X^TX)，有时样本数非常大时，不计算量非常大。SVD的实现可以不先求协方差矩阵(X^TX)也能求出右厅异阵V，使用SVD算法进行PCA降维时可以不用做特征分解。

SVD可以实现并行化，加速数据处理。