数据降维的目的：

1. 发现隐含特征
2. 移除噪声
3. 方便解释和可视化

SVD分解

SVD原理

SVD分解的一般形式：
$\mathbf{A}_{[m \times n]}=\mathbf{U}_{[m \times r]} \Sigma_{[r \times r]}\left(\mathbf{V}_{[n \times r]}\right)^{\top}$A[m×n]​=U[m×r]​Σ[r×r]​(V[n×r]​)⊤
其中：以用户和电影之间的评分来讨论这一问题，方便理解。
$A$A：输入矩阵，例如：用户和电影之间的评分矩阵
$U$U：列正交矩阵（$m*r$m∗r），且每一列均为单位向量，可以理解为用户和电影种类（或者说Latent factors）之间的关联矩阵
$\Sigma$Σ：对角阵（$r*r$r∗r），根据矩阵$A$A提供的信息多少，显示每个种类（或者说Latent factors）的strength，且对角阵上的值按降序排列。
$V^\top$V⊤：行正交矩阵（$n*r$n∗r），且每一行为单位向量，表示每部电影和电影种类（或者说Latent factors）之间的关联矩阵。

结合上图，简单理解下SVD分解的含义。矩阵$U$U是user-to-concept矩阵，比较每行中三个值的大小，不难发现，第一列中前四行的值较大，刚好对应user-to-movie矩阵中，前四个用户均喜欢观看科幻类电影；矩阵$\Sigma$Σ是每个种类的电影所占的比例，由于在user-to-movie矩阵中，用户对科幻类电影的打分项明显高于浪漫类，所以在矩阵$\Sigma$Σ中科幻类电影的比重较大；矩阵$V^\top$V⊤是电影种类和电影之间的关联程度，不难发现第一行前三个的值第一行后两个的值，刚好对应上前三部电影是科幻类。
在上面的例子中，我们不难发现，第五个和第七个用户虽然大部分的观影是浪漫类，但也存在科幻类的观影。正是由于此原因造成分解时电影种类有三类，但是实际上可以将$\Sigma$Σ对角阵上较小的值置为0，接下来将证明这一点。
假设矩阵$M$M的$SVD$SVD分解为$M=PQR$M=PQR，则：
$||M||^2=\sum_{i}\sum_{j}\left(m_{ij}\right)^2=\sum_{i}\sum_{j}\left(\sum_{k}\sum_{m}p_{ik}q_{km}r_{mj}{}\right)^2$∣∣M∣∣2=i∑​j∑​(mij​)2=i∑​j∑​(k∑​m∑​pik​qkm​rmj​)2
由于矩阵$Q$Q为对角阵：
$\sum_{k}\sum_{m}p_{ik}q_{km}r_{mj}=\sum_{k}p_{ik}q_{kk}r_{kj}$k∑​m∑​pik​qkm​rmj​=k∑​pik​qkk​rkj​
则：
$||M||^2=\sum_{i}\sum_{j}\sum_{k}\sum_{l}p_{ik}q_{kk}r_{kj}p_{il}q_{ll}r_{lj}$∣∣M∣∣2=i∑​j∑​k∑​l∑​pik​qkk​rkj​pil​qll​rlj​
由于矩阵$P$P、$R$R为列正交矩阵，且每一列为单位向量，则：
$||M||^2=\sum_{i}\sum_{j}\sum_{k}p_{ik}p_{ik}q_{kk}q_{kk}r_{kj}r_{kj}=\sum_{i}\sum_{j}\sum_{k}p_{ik}^2q_{kk}^2r_{kj}^2=\sum_{k}q_{kk}^2$∣∣M∣∣2=i∑​j∑​k∑​pik​pik​qkk​qkk​rkj​rkj​=i∑​j∑​k∑​pik2​qkk2​rkj2​=k∑​qkk2​
假设$A=U\Sigma V^\top$A=UΣV⊤、$B=USV^\top$B=USV⊤，矩阵$S$S的前$k$k个对角线的值与矩阵$\Sigma$Σ的前$k$k个相同，后面的值为0。则：
$||A-B||=||U\Sigma V^\top-USV^\top||=||U\left(\Sigma-S\right)V^\top||$∣∣A−B∣∣=∣∣UΣV⊤−USV⊤∣∣=∣∣U(Σ−S)V⊤∣∣
可见$||A-B||$∣∣A−B∣∣的误差与$\Sigma$Σ矩阵的后几个对角线值的平方等价，所以在对$SVD$SVD分解进行降维时，直接将对角矩阵上较小的值置为0是有道理的。

计算SVD分解矩阵

设矩阵$M$M的SVD分解为$M=U \Sigma V^{\mathrm{T}}$M=UΣVT，则$M^{\mathrm{T}}=\left(U \Sigma V^{\mathrm{T}}\right)^{\mathrm{T}}=\left(V^{\mathrm{T}}\right)^{\mathrm{T}} \Sigma^{\mathrm{T}} U^{\mathrm{T}}=V \Sigma^{\mathrm{T}} U^{\mathrm{T}}=V \Sigma U^{\mathrm{T}}$MT=(UΣVT)T=(VT)TΣTUT=VΣTUT=VΣUT，$M^{\mathrm{T}} M=V \Sigma U^{\mathrm{T}} U \Sigma V^{\mathrm{T}}=V \Sigma^{2} V^{\mathrm{T}}$MTM=VΣUTUΣVT=VΣ2VT，两边同时乘$V$V，$M^{\mathrm{T}} M V=V \Sigma^{2} V^{\mathrm{T}} V=V \Sigma^{2}$MTMV=VΣ2VTV=VΣ2，故矩阵$M^\top M$M⊤M的特征向量组就是所求的$V$V，其特征根的平方根就是对角阵$\Sigma$Σ，同理，可以求出矩阵$U$U。

SVD应用

现在有某个用户对于所看电影打分为$\begin{bmatrix}5 & 0 &0&0&0\end{bmatrix}$[5​0​0​0​0​]，现在将此向量乘以矩阵$V$V，得到$\begin{bmatrix}2.8&0.6\end{bmatrix}$[2.8​0.6​]，可以推断出该用户更加喜欢科幻类的电影，在这里，也可以理解矩阵$V$V为新的坐标轴
但$SVD$SVD分解存在的问题是当矩阵比较稀疏时，分解得到的矩阵将会特别稠密。

CUR分解

$CUR$CUR分解的一般形式：
$A=CUR$A=CUR
其中，矩阵$A$A为输入矩阵（$m*n$m∗n）
$C$C：在矩阵$A$A中随机选择$r$r列所形成，$m*r$m∗r
$R$R：在矩阵$A$A中随机选择$r$r行所形成，$r*n$r∗n
$U$U：$r*r$r∗r
矩阵$C$C、$R$R的选择策略：

假设矩阵$W$W为矩阵$C$C、$R$R的交叉部分，且矩阵的$W$W的$SVD$SVD分解为$W=X\Sigma Y^\top$W=XΣY⊤，$\Sigma^+$Σ+为$\Sigma$Σ的逆矩阵或者伪逆矩阵，$U=Y\left(\Sigma^{+}\right)^{2} X^{\mathrm{T}}$U=Y(Σ+)2XT