在先前的文章PCA主成分分析Python实现中介绍了一种降维方法，本文主要介绍另一种方法：SVD(Singular Value Decomposition，奇异值分解)。该算法在推荐系统中经常用到，而且也可用于降维，PCA的实现除了通过求解协方差矩阵、特征值、特征向量来计算以外，还可以使用SVD来求解，具体细节本文就不讨论了，下面主要来介绍下SVD的推导。
基本理论
- 对于$n$阶方阵$A$，有$Ax=\lambda x$，则$\lambda$特征值，$x$特征向量;
- 如果向量$\vec{a}$和向量$\vec{b}$正交，则$\vec{a} \cdot \vec{b} = 0$;
- 一个内积空间的正交基（orthogonal basis）是元素两两正交的基,基中的元素称为基向量。如果一个正交基的基向量的模长都是单位长度1，则称这正交基为标准正交基或”规范正交基”（Orthonormal basis）；
- A与A的转置矩阵是有相同的特征值,但是他们各自的特征向量没有关系；
SVD推导
Step1：矩阵分解
对于矩阵$A$，有$A^TA = \lambda_{i} v_{i}$，其中$\lambda_{i}$为特征值，$v_{i}$为特征向量。假定$(v_{i}, v_{j})$是一组正交基，那么有$v_{i}^{T} \cdot v_{j} = 0$，那么：
$$
\begin{align}
(Av_{i}, Av_{j})
&= (Av_{i})^{T} \cdot Av_{j} \\
&= v_{i}^{T} A^T Av_{j} \\
&= v_{i}^{T} \lambda_{j} v_{j} \\
&= \lambda_{j} \color{red}{v_{i}^{T} v_{j}} \\
&= 0
\end{align}
\label{1}\tag{1}
$$
可以得出$Av_{i}, Av_{j}$也是一组正交基，根据公式\eqref{1}可以推导出$(Av_{i}, Av_{i}) = \lambda_{i} v_{i}^{T} v_{i}=\lambda_{i} $，从而可以得到：
$$
\begin{align}
& |Av_{i}|^2 = \lambda_{i} \\
& |Av_{i}| = \sqrt{\lambda_{i}}
\end{align}
\label{2}\tag{2}
$$
根据公式\eqref{2}，有 $\frac{Av_{i}}{|Av_{i}|} = \frac{1}{\sqrt{\lambda_{i}}} Av_{i}$，令$ \frac{1}{\sqrt{\lambda_{i}}} Av_{i}= u_{i}$，可以得到
$$
Av_{i}= \sqrt{\lambda_{i}}u_{i}=\delta_{i}u_{i}
\label{3}\tag{3}
$$
其中$\delta_{i} = \sqrt{\lambda_{i}}$，得到这个表达之后，我们可以进一步推导：
$$
\begin{align}
AV &= A(v_{1}, v_{2}, \dots, v_{n} ) \\
&= (Av_{1}, Av_{2}, \dots, Av_{n} ) \\
&= (\delta_{1}u_{1}, \delta_{2}u_{2}, \dots, \delta_{n}u_{n} ) \\
&= U\Sigma
\end{align}
\label{4}\tag{4}
$$
从而可以得出：
$$
A = U\Sigma V^T
\label{5}\tag{5}
$$
Step2：矩阵计算
得到矩阵$A$的表示之后，我们应该如何计算向量$U$和$V$呢？继续往下面分析：
首先计算出$A$的转置$A^T$:
$$
\begin{align}
A^T = V\Sigma^TU^T
\end{align}
\label{6}\tag{6}
$$
得到$A$的转置之后，我们接下来计算$A^TA$值：
$$
\begin{align}
A^TA
&= V\Sigma^TU^T U\Sigma V^T \\
&= V\Sigma^2V^T
\end{align}
\label{7}\tag{7}
$$
通过公式\eqref{7}，可以得到$A^TA v_{i} = \lambda_{i}v_{i}$，只需要求出$A^TA$的特征向量即可得到$V$.
同理可得$AA^T$的值：
$$
\begin{align}
A A^T
&= U\Sigma V^T V\Sigma^TU^T \\
&= U\Sigma^2U^T
\end{align}
\label{8}\tag{8}
$$
通过公式\eqref{8}，可以得到$AA^T u_{i} = \lambda_{i}u_{i}$，只需要求出$AA^T$的特征向量即可得到$U$.
Conclusion
SVD将矩阵分解为$U$和$V$，得到$A = U\Sigma V^T$。我们可以取前k个非零奇异值，将这k个对应的奇异向量合并来进行降维。SVD还可以用于PCA的求解过程，主要用到SVD的右奇异矩阵$V$。