SVD和PCA详细原理以及联系（包含公式推导）

初始假设

假设$X \in R^{n \times d}$X∈Rn×d，即为$n$n个样本，$d$d维的矩阵，将每个数据矢量的条目合并，使得$X_i^T = (X_i1, \ldots, X_id)$XiT​=(Xi​1,…,Xi​d)。 在将这些向量放入数据矩阵之前，我们实际上会减去数据的平均值，即：$\mu = \frac{1}{n} \sum_{i=1}^n X_i = (\sum_{i=1}^n X_i1, \ldots, X_id)^T$μ=n1​i=1∑n​Xi​=(i=1∑n​Xi​1,…,Xi​d)T
然后用每一列减去$\mu^T$μT，得到零中心向量作为矩阵的行：
$X = \begin{pmatrix} X_1^T - \mu ^T \\ \\ X_2^T - \mu ^T \\ \ldots \\ \\ X_n^T - \mu ^T \end{pmatrix}$X=⎝⎜⎜⎜⎜⎜⎜⎛​X1T​−μTX2T​−μT…XnT​−μT​⎠⎟⎟⎟⎟⎟⎟⎞​
样本的协方差$S$S为：
$S = \frac{1}{n - 1} \sum_{i=1}^n (X_i - \mu )(X_i - \mu ) ^T = \frac{1}{n - 1} X ^T X$S=n−11​i=1∑n​(Xi​−μ)(Xi​−μ)T=n−11​XTX

主成分分析（PCA）

主成分分析(PCA)是一种数据降维技巧，它能将大量相关变量转化为一组很少的不相关变
量，这些无关变量称为主成分。例如，使用PCA可将30个相关(很可能冗余)的环境变量转化为5个无关的成分变量，并且尽可能地保留原始数据集的信息，即使这些成分变量对“原始方差”的贡献程度尽可能大。
PCA是找到一个$k \leq d$k≤d的单位向量的集合$V_i \in R^d(i = 1,2, \ldots, k)$Vi​∈Rd(i=1,2,…,k)，称为主成分PC，其满足：投影到由$V_i$Vi​确定方向上的数据集方差被最大化，且$V_i$Vi​被选择与之正交。
现在，将矢量$X \in R^d$X∈Rd投影到由任何$V_i$Vi​确定的方向上，可以简单的写成点积$V_i^T ·X$ViT​⋅X，这意味着投影到第一个主成分$V_1$V1​上的数据集的方差可以写为：
$\frac{1}{n - 1} \sum_{i = 1}^n (V_1 ^TX_i - V_1 ^T \mu ) ^2 = V_1 ^T ·S·V_1$n−11​i=1∑n​(V1T​Xi​−V1T​μ)2=V1T​⋅S⋅V1​
在$V_1^T V_1= 1$V1T​V1​=1的前提下取最大化$V_1$V1​的值，此时有：$S V_1 = \lambda_1 V_1$SV1​=λ1​V1​，意味着$V_1$V1​是协方差矩阵S的特征向量，相应的特征值恰好等于沿$V_1$V1​数据集的方差：
$V_1^ T S V_1 = \lambda_1$V1T​SV1​=λ1​
将数据投影到新方向$V_2$V2​上继续此过程，同时强制要求$V_1$V1​与$V_2$V2​正交，然后在$V_3$V3​与$V_1$V1​、$V_2$V2​正交的条件下寻找$V_3$V3​，以此类推，最终的结果是$X$X的第一个$k$k主成分恰好对应由它们特征向量排序的协方差矩阵$S$S的特征向量，特征值恰好等于沿对应特征向量的数据集方差。
此结果表明了$S$S上有一整套正交的特征向量，$S$S为对称矩阵，满足$S = S^T$S=ST，取$k = d$k=d个主成分，构造一个$d \times d$d×d的矩阵$V$V，列为$S$S的特征向量，$S$S为：
$S = V \wedge V^T = \sum_{i = 1} ^r \lambda_i V_i V_i ^T (\land = diag(\lambda_1, \ldots, \lambda_d)$S=V∧VT=i=1∑r​λi​Vi​ViT​(∧=diag(λ1​,…,λd​)

奇异值分解（SVD）

奇异值分解上一种矩阵分解方法，相较于特征值分解只能针对方阵，它可以分解几乎任何矩阵，是目前为止可以说是最好的矩阵分解方法。任意矩阵$A \in R^{n \times d}$A∈Rn×d的奇异值分解可以看作为线性变换时，$A$A将单位球面$S^d \subset R ^d$Sd⊂Rd映射到$R^n$Rn中的超椭圆：

椭圆$AS^d \in R ^n$ASd∈Rn的半轴长度$\sigma_i$σi​是$A$A的奇异值，沿着半轴的单位向量$u_i$ui​称为$A$A的“左”奇异向量，单位向量$v_i$vi​是$A$A的“右”奇异向量，$r = rank(A)$r=rank(A)，即r是A的秩。下为奇异值分解的具体方法：
$U = [u_1, \ldots, u_n] \in R^{n \times n}$U=[u1​,…,un​]∈Rn×n$\Sigma = diag[\sigma_1, \ldots, \sigma_n] \in R^{n \times d}$Σ=diag[σ1​,…,σn​]∈Rn×d$V = [v_1, \ldots, v_d] \in R^{d \times d}$V=[v1​,…,vd​]∈Rd×d$AV = U \Sigma$AV=UΣ故有：$A = U \Sigma V^T$A=UΣVT
即将矩阵$A$A分解为右边三个矩阵相乘，其中，$U、V$U、V为正交矩阵，$\Sigma$Σ只有对角元素而且对角元素是从大到小排列的，这些对角元素称为奇异值。在几何中，我们可以把矩阵看做空间上的线性变换，而奇异值分解的几何含义是：对于任何的一个矩阵，我们都能找到一组坐标轴，它是由原来的坐标轴通过旋转和缩放得到的。奇异值的含义就是这组变换后新的坐标轴的长度。

矩阵$A$A的作用是将一个向量从$V$V这组正交向量空间中旋转到$U$U空间，并按照$\Sigma$Σ在各个方向上做了缩放，缩放倍数就是奇异值。 由简单的矩阵乘法可得：
$A^T A = V \Sigma^2 V^T$ATA=VΣ2VT$A A^T = U \Sigma^2 U^T$AAT=UΣ2UT因此$V$V是$A^T A$ATA的特征向量，$U$U是$A A^T$AAT的特征向量，奇异值的平方$\sigma^2$σ2是$A^T A$ATA和$A A^T$AAT共同的特征值，再将奇异值从大到小排列，前$k$k个奇异值可以近似描述矩阵$A = U \Sigma V^T$A=UΣVT。

PCA与SVD的联系

PCA的运行原理很简单，就是对原始的空间中顺序地找一组组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第一、二个轴正交的平面中方差最大的。这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间（因为维数越靠后的空间轴的重要性是依次降低的），这样就从一个N维的空间转化到到r维的空间了，虽然这样做会使得数据有所损失，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。SVD得出的奇异向量也是从奇异值由大到小排列的，从PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量，依此类推，由于推导公式比较繁琐，故下面我用手写的方式说明二者之间的联系：
如果要对行进行压缩只需要在$A = U \Sigma V^T$A=UΣVT的左边乘上$U$U的转秩即可。可以说，PCA是对SVD的一个包装和使用，如果我们实现了SVD，那也就自然而然实现了PCA，而且相较于单纯的对$A^T A$ATA进行特征值分解只得到一个方向上的PCA更好的地方是，有了SVD，我们就可以得到两个方向的PCA。

由于本人所学有限，如有错误，还望指正。