原始数据通常具有较高的维数导致维数灾难，通过降维（Dimensionality reduction）可以消除数据冗余与数据噪声，降低算法的计算开销，使得数据更加易用，结果更加易懂。

1. 主成分分析

主成分分析（PCA，Principal Component Analysis）将数据从原来的坐标系转换到新的坐标系，新坐标系的选择由数据本身决定。

1.1 问题定义

n维正交空间中，坐标系W n = { w 1 , w 2 , . . . , w n } ，其中w 是标准正交基，即 0

m个样本数据 （已中心化）。

其中

将m 个数据的维度从n 维降到n ′ 维（通常由用户指定），新的坐标系 样本点 x ^{( i )} 在新的n ′  维坐标系中投影：

是 x ⁱ 在低维坐标系中第j 维的坐标。

使用 z ⁱ 恢复原始数据x i ，则得到的恢复数据

1.2 优化目标

降维相当于使用一个超平面对样本进行表达，该超平面具有以下性质

• 最近重构性：样本点到这个超平面距离足够近
• 最大可分性：样本点在这个超平面上的投影尽可能分开

（1）基于最小投影距离

希望m 个n ′ 维的数据集尽可能的代表原始数据集，即数据从n 维降到n ′ 维的损失尽可能小，优化目标为

由于 是数据集的协方差矩阵，为常量，优化目标等价于：

（2）基于最大投影方差

对于任意一个样本x ^{( i )} ，在新的坐标系中的投影为 ，在新坐标系中的投影方差为

要使所有的样本的投影方差和最大，也就是最大化 的迹，即：

可以看出最近重构性等价于最大可分性。

1.3 问题求解

使用拉格朗日乘子法，引入拉格朗日函数

对W 求导，令导数等于0得，

W为X x ^t的n ′ 个特征向量组成的矩阵，而λ 为X x ^t 的若干特征值组成的矩阵，特征值在主对角线上，其余位置为0。将数据集从n 维降到n ′ 维时，需要找到最大的n ′个特征值对应的特征向量。

对协方差矩阵X x ^t进行特征值分解，将求得的特征值排序：

取前n ′ 个特征值对应的特征向量构成解

实践中，一般对X 进行奇异值分解代替协方差矩阵的特征值分解。

2. SVD

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

2.1 特征分解

A是一个n 阶矩阵，若λ 和n 维非零向量x 满足：

则λ是矩阵A 的一个特征值，x是矩阵A 对应特征值λ的特征向量。

∣ λ E − A ∣ 称为A 的特征多项式，当特征多项式等于0的时候，称为A 的特征方程，特征方程是一个齐次线性方程组，求解特征值的过程就是求解特征方程的解。

矩阵A的n 个特征值λ 1 ≤ λ 2 ≤ . . . ≤ λ n，以及这n 个特征值所对应的特征向量{ w 1 , w 2 , . . . w n } ，如果这n 个特征向量线性无关，那么矩阵A就可以用下式的特征分解表示：

其中，W 是这n 个特征向量所张成的n × n 矩阵，而Σ 为这n 个特征值为主对角线的n × n 阶矩阵。

一般会把W 的n 个特征向量标准化，即满足∣ ∣  w ⁱ∣ ∣ 2 = 1 或者说 ，此时W 的n特征向量为标准正交基，满足 w ^T w = I ，即 w ^T =  w ^-1  ， 也就是说W为酉矩阵。

此时特征分解表达式可以写成：

2.2 SVD

要进行特征分解，矩阵A 必须为方阵，那么如果A不是方阵，即行和列不相同时，需要使用SVD。

假设矩阵A 是一个m × n的矩阵，定义矩阵A 的SVD为：

其中U 是一个m × m 的矩阵，V是一个n × n 的矩阵。U 和V 称为A的左/右奇异向量矩阵，都是酉矩阵，即满足u ^T u = I , v ^T v  = I

Σ 是一个m × n的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，通常将奇异值由大到小排列，这样Σ 便能由A 唯一确定。

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

其中k 要比n 小很多，即一个大的矩阵A 可以用三个小的矩阵 来表示：

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