原理

奇异值分解（Singular Value Decomposition，SVD）是机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。

特征值与特征向量回顾

我们首先回顾下特征值和特征向量的定义如下：

\[Ax = \lambda x\]

其中A是一个\(n \times n\)的实对称矩阵，x是一个n维向量，则我们说λ是矩阵A的一个特征值，而x是矩阵A的特征值λ所对应的特征向量。

矩阵对角化：

  • 先求特征值,如果没有相重的特征值，所有特征根都不相等,那么不用说,绝对可以对角化；
  • 如果有相重的特征值\(\lambda_k\),其重数为k,那么你通过解方程\((\lambda_k E-A)x=0\)得到的基础解系中的解向量若也为k个，则A可对角化；若小于k，则A不可对角化。

求出特征值和特征向量有什么好处呢？就是我们可以将矩阵A特征分解。如果矩阵A可对角化，并且我们求出了矩阵A的n个特征值\(\lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n\)，以及这n个特征值所对应的特征向量\({w_1, w_2,...,w_n}\)，如果这n个特征向量线性无关，那么矩阵A就可以用下式的特征分解表示：

\[A=W\Sigma W^{-1}\]

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

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

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

\[A=W\Sigma W^T\]

矩阵可以理解为对向量的拉伸，旋转，投影。而对于方阵而言，不存在维度升降的投影，因此：

  • 特征值就是拉伸的大小
  • 特征向量指明了拉伸的方向

给定任意的一个向量x，我们如何求Ax呢？ 很简单，把x沿着\(w_1, w_2,...\)分解，然后分别按照各自的比例\(\lambda_1, \lambda_2,...\)伸缩 最后再求和即可。

一定要这样分解吗？不能直接拉伸，旋转吗？当你运算\(A^n x\)的时候，我们就发现这里的这样分解的好处了。沿着各个P的伸缩量正好是\(\lambda^n\)。

所以，特征值在动态系统分析中是描述系统稳定性的非常重要的量，它决定了离散系统在空间内某个方向上的变化趋势（是无限扩张(\(\lambda>1\))？还是收缩(\(\lambda<1\))？还是保持不变(\(\lambda=1\))？），这是判断离散线性系统的重要特征。

特征值分解也就很好定义。 一个可对角化的方阵A：

分解为：\(A=W\Sigma W^{-1}\) ，P的列向量为特征向量（\(W=[w_1,w_2,...]\)）。

理解为：以W为基的坐标分解变换+伸缩变换+以P为基坐标还原变换。

注意到要进行特征分解，矩阵A必须为方阵。那么如果A不是方阵，即行和列不相同时，我们还可以对矩阵进行分解吗？答案是可以，此时我们的SVD登场了。

SVD

SVD也是对矩阵进行分解，但是和特征分解不同，SVD并不要求被分解的矩阵为方针。假设我们的矩阵A是一个\(m \times n\)的矩阵，那么我们定义矩阵A的SVD为：

\[A=U \Sigma V^T\]

其中U是一个\(m \times n\)的矩阵，\(\Sigma\)是一个\(m \times n\)的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，V是一个\(n \times n\)的矩阵。U和V都是酉矩阵，即满足\(U^T U=I, V^T V= I\)。下图可以形象地看出SVD的定义：

那么如何求解SVD分解后的\(U,\Sigma, V\)这三个矩阵呢？

如果我们将\(A^T\)和A做矩阵乘法，那么会得到\(n \times n\)的一个方阵\(A^T A\)。既然\(A^T A\)是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：

\[(A^T A)v_i=\lambda_i v_i\]

这样我们就可以得到矩阵\(A^T A\)的n个特征值和对应的n个特征向量v了。将\(A^T A\)的所有特征向量张成一个\(n \times n\)的矩阵V，这就是我们SVD公式里面的V矩阵了。一般我们将V中的每个特征向量叫做A的右奇异向量。

如果我们将A和\(A^T\)做矩阵乘法，那么会得到\(m \times m\)的一个方阵\(AA^T\)。既然\(AA^T\)是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：

\[(AA^T)u_i=\lambda_i u_i\]

这样我们就可以得到矩阵\(AA^T\)的m个特征值和对应的m个特征向量u了。将\(AA^T\)的所有特征向量张成一个\(m \times m\)矩阵U，就是我们SVD公式里面的U矩阵了。一般我们将U中的每个特征向量叫做A的左奇异向量。

U和V我们都求出来了，现在就剩下奇异值矩阵\(\Sigma\)没有求出了。由于\(\Sigma\)除了对角线上的是奇异值，其他位置都是0，那我们只需要求出每个奇异值\(\sigma\)就可以了。

我们注意到：

\[\begin{align} &A = U\Sigma V^T \\ &\Rightarrow AV = U\Sigma V^TV \\ &\Rightarrow AV = U\Sigma = \sigma_i u_i \\ &\Rightarrow \sigma_i = Av_i/u_i \\ \end{align}\]

这样我们可以求出我们的每个奇异值，进而求出奇异值矩阵\(\Sigma\)。

上面还有一个问题没有讲，就是我们说\(A^TA\)的特征向量组成的就是我们SVD中的V矩阵，而\(AA^T\)的特征向量组成的矩阵就是我们SVD中的U矩阵，这其实很容易证明，我们以V矩阵的证明为例。

\[\begin{align} &A=U\Sigma V^T \\ &\Rightarrow A^T = V\Sigma^T U^T \\ &\Rightarrow A^TA = V\Sigma^T U^T U\Sigma V^T = V\Sigma^2 V^T \\ \end{align}\]

上式证明使用了：\(U^TU=I, \Sigma^T\Sigma=\Sigma^2\)。可以看出\(A^TA\)的特征向量组成的矩阵的确就是我们SVD中的V矩阵。类似的方法可以得到\(AA^T\)的特征向量组成的矩阵就是我们SVD中的U矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：

\[\sigma_i = \sqrt{\lambda_i}\]

这样也就是说，我们可以不用\(\sigma_i = Av_i/u_i\)来计算奇异值，也可以通过求出\(A^TA\)的特征值取平方根来求奇异值。

对于奇异值，它跟我们特征分解中的特征值类似，在奇异值矩阵中按照从大到小排列，而且奇异值的减少特别快，在很多情况下，前10%甚至1%的奇异值的和就占了全部奇异值之和的99%以上的比例。也就是说，我们也可以用最大k个奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：

\[A_{m \times n} = U_{m \times m} \Sigma_{m \times n} V_{n \times n}^T \approx U_{m \times k} \Sigma_{k \times k} V_{k \times n}^T\]

其中k要比n小很多，也就是一个大的矩阵A可以用三个小的矩阵\(U_{m \times k}，\Sigma_{k \times k}，V_{k \times n}^T\)来表示。如下图所示，现在我们矩阵A只需要灰色的部分的三个小矩阵就可以近似描述了。

由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户的喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP算法，比如潜在语义索引（LSI）。

奇异值分解也是为了简化矩阵运算的一种方式。它和特征值变换的基本理念不同，看似繁琐一点，却能道出线性变换的一般本质。

定义：任何\(A \in R^{m \times n}\)（而不仅仅是可对角化的方阵）的矩阵都可以如下分解：\(A=U\Sigma V^T\)

其中U和V是正交矩阵（复数域里面是酉矩阵），\(\Sigma\)是由对角阵和零矩阵合成的矩阵。

它的含义是任何A的变换可以理解为 一个正交变换+伸缩变换+另一个正交变换。（正交变换可以暂时理解为 “不改变大小以及正交性”的旋转/反射 等变换）这是对一般线性变换的本质的阐释。

参考文献