10.5高维PCA

10.5 高维PCA

为了进行PCA，我们需要计算数据的协方差矩阵。在D维空间中，数据协方差矩阵是一个D\times D的矩阵。计算这个矩阵的特征值和特征向量在计算上是昂贵的，因为它与D的三次方成正比。因此，正如我们之前讨论的那样，PCA在非常高维的情况下是不可行的。例如，如果我们的x_n是包含10,0000个像素的图像（例如，100\times100像素的图像），那么我们需要计算一个10,000\times10,000的协方差矩阵的特征分解。以下，我们针对数据点数量远小于维度的情况（即N\ll D）提供了一种解决方案。

假设我们有一个已居中的数据集x_1,\ldots,x_N，其中x_n\in\mathbb{R}^D。那么，
数据的协方差矩阵定义为

(10.53)

其中X=[x_1,\ldots,x_N]是一个D\times N的矩阵，其列是数据点。

我们现在假设N\ll D，即数据点的数量小于数据的维度。如果没有重复的数据点，协方差矩阵S的秩为N，因此它有D-N+1个特征值为0。直观地说，这意味着存在一些冗余。接下来，我们将利用这一点，将D\times D的协方差矩阵转换为一个N\times N的协方差矩阵，其所有特征值都是正的。

在PCA中，我们最终得到了特征向量方程

(10.54)

其中b_m是主子空间的一个基向量。让我们重写这个方程：根据(10.53)中定义的S，我们得到

(10.55)

我们现在从左侧乘以X^\top\in\mathbb{R}^{N\times D}，得到
(10.56)

我们得到了一个新的特征向量/特征值方程：\lambda_m仍然是特征值，这证实了我们在第4.5.3节中的结果，即XX^\top的非零特征值等于X^\top X的非零特征值。我们得到与\lambda_m相关联的矩阵\frac1NX^\top X\in\mathbb{R}^{N\times N}的特征向量为\boldsymbol{c}_m:=\boldsymbol{X}^\top\boldsymbol{b}_m。假设我们没有重复的数据点，则该矩阵的秩为N且是可逆的。这也意味着\frac1NX^\top X与数据协方差矩阵S具有相同的（非零）特征值。但现在这是一个N\times N的矩阵，因此我们可以比原始的D\times D数据协方差矩阵更有效地计算特征值和特征向量。既然我们已经得到了\frac1NX^\top X的特征向量，我们接下来将恢复原始的特征向量，这在PCA中仍然需要。目前，我们知道\frac1NX^\top X的特征向量。如果我们用X左乘我们的特征值/特征向量方程，我们得到

(10.57)

并且我们再次恢复了数据协方差矩阵。这也意味着我们现在恢复了Xc_m作为S的一个特征向量。

备注：如果我们想应用我们在第10.6节中讨论的PCA算法，我们需要将S的特征向量Xc_m归一化，使它们的范数为1。