一、主成分析PCA

1、所解决问题

给定 $m$ 个 $n$ 维样本$X=\{x_0,x_1,…,x_m\}$ ，通过变换 $y=Px$ (其中 $P_{k\times n}$ 为变换矩阵)，将样本 $(x_i)_{i=0,…,m}$ 从 $n$ 维降到 $k$ 维 $(y_i)_{i=0,…,m}$ ，计$Y=\{y_0,y_1,…,y_m\}$ ，同时最大程度的减少降维带来的信息损失。

2、所依赖的原则

根据降维并减小信息损失的目标，可以得出以下两个原则

降维后的各个维度之间相互独立，即去除降维之前样本 $x$ 中各个维度之间的相关性。
最大程度保持降维后的每个维度数据的多样性，即最大化每个维度内的方差

记降维后样本集 $Y$ 的协方差矩阵为

$B_{k\times k} = \frac{1}{m}YY^T$

上述第一个条件要求协方差矩阵$B$除了对角线上元素外，其他均为0，也即 $B$ 为对角矩阵。

将变换关系 $y=Px$ 代入Y的协方差矩阵B中，

$B_{k\times k}=\frac{1}{m}YY^T = \frac{1}{m}PX(PX)^T=P\frac{1}{m}XX^TP=P_{k\times n}C_{n \times n}P_{n\times k}^T \tag{1}$

其中， $C_{n\times n} = \frac{1}{m}XX^T$ 是变换前数据 $X$ 的协方差矩阵。

$C_{n\times n}$ 的特征值分解形式如下：

$D_{n\times n} = Q_{n\times n}C_{n\times n} Q_{n\times n}^T \tag{2}$

其中， $D_{n\times n}$ 为对角矩阵。

明显的式(1)和式(2)除了维度不同，其他均一样。

结合上述第二条原则，变换矩阵 $P_{k\times n}$ 即是矩阵$C$的前$k$大的特征向量按行组成的矩阵。

3、问题求解方法

式2就是协方差矩阵 $C$ 的特征值分解，变换矩阵 $P_{k\times n}$ 即是矩阵$C$的前$k$大的特征向量按行组成的矩阵。所以，PCA的求解步骤为：

求 $X$ 均值
将 $X$ 减去均值
计算协方差矩阵 $C=\frac{1}{m}XX^T$
对协方差矩阵 $C$ 特征值分解
从大到小排列 $C$ 的特征值
取前 $k$ 个特征值对应的特征向量按行组成矩阵即为变换矩阵 $P_{k\times n}$

这里的核心问题是协方差矩阵 $C=\frac{1}{m}XX^T$ 的特征值分解。

二、奇异值分解SVD

1、所解决问题

$A_{m\times n} = U_{m\times m} \Sigma_{m\times n}V_{n \times n}^T$

其中 $U_{m\times m}$ 和 $V_{n \times n}$ 均为正交矩阵， $\Sigma_{m\times n}$ 为对角矩阵

奇异值分解要解决的问题是将 $A_{m\times n}$ 矩阵分解为对角矩阵 $\Sigma_{m\times n}$ ，$\Sigma_{m\times n}$中对角元素 $\sigma_i$ 称为矩阵 $A_{m\times n}$ 的奇异值

2、问题求解方法

$AA^T=U\Sigma V^T V\Sigma^T U^T = U\Sigma\Sigma^T U^T$ $A^TA=V\Sigma^T U^T U\Sigma V^T = V\Sigma^T \Sigma V^T$

需要指出的是，这里 $\Sigma\Sigma^T$ 与$\Sigma^T \Sigma$在矩阵的角度上来讲，它们是不相等的，因为它们的维数不同$\Sigma \Sigma^T\in R^{m\times m}$，而$\Sigma^T \Sigma \in R^{n\times n}$，但是它们在主对角线的奇异值是相等的，即有
$\Sigma\Sigma^T=\begin{bmatrix} \sigma_1^2&0&0&0 \\ 0&\sigma_2^2&0&0\\ 0&0&\ddots&0\\ 0&0&0&\ddots \end{bmatrix}_{m \times m} \qquad \Sigma^T\Sigma=\begin{bmatrix} \sigma_1^2&0&0&0 \\ 0&\sigma_2^2&0&0\\ 0&0&\ddots&0\\ 0&0&0&\ddots \end{bmatrix}_{n \times n}$

所以 $U$ 是 $AA^T$ 特征值分解的特征向量按列组成的正交矩阵,$V$ 是 $A^TA$ 特征值分解的特征向量按列组成的正交矩阵， $\Sigma\Sigma^T,\Sigma^T\Sigma$ 是$AA^T,A^TA$ 特征值组成的对角矩阵，也可以看出 $A_{m\times n}$ 的奇异值 $\sigma_i$ 是 $A^TA,A^TA$ 特征值 $\lambda_i$ 的平方根。

奇异值分解的关键在于对 $A^TA,AA^T$ 进行特征值分解。

三、PCA与SVD的关系

由上述分析可知，

PCA求解关键在于求解协方差矩阵$C=\frac{1}{m}XX^T$的特征值分解
SVD关键在于 $A^TA,A^TA$ 的特征值分解。
很明显二者所解决的问题非常相似，都是对一个实对称矩阵进行特征值分解，

如果取：

$A=\frac{X^T}{\sqrt{m}}$

则有：

$A^TA=(\frac{X^T}{\sqrt{m}})^T \frac{X^T}{\sqrt{m}}=\frac{1}{m}XX^T$

其实，PCA只与SVD的右奇异向量的压缩效果相同。

如果取 $V$的前 $k$ 行作为变换矩阵 $P_{k\times n}$ ，则 $Y_{k\times m} = P_{k\times n }X_{n\times m}$ ，起到压缩行即降维的效果

如果取 $U$的前 $d$ 行作为变换矩阵 $P_{d\times m}$ ，则 $Y_{n\times d} = X_{n\times m}P_{m\times d}$ ，起到压缩列即去除冗余样本的效果。