10.4特征向量计算和低秩近似

10.4 特征向量计算和低秩近似

在前面的章节中，我们获得了主成分子空间的基础，即与数据协方差矩阵最大特征值相关联的特征向量

(10.45)

(10.46)

注意，X 是一个 D\times N 矩阵，即它是“典型”数据矩阵的转置（Bishop, 2006; Murphy, 2012）。为了得到 S 的特征值（以及对应的特征向量），我们可以采用两种方法：

\bullet 我们进行特征分解（参见第 4.2 节）并直接计算 S 的特征值和特征向量。

\bullet 我们使用奇异值分解（参见第 4.5 节）。由于 S 是对称的，并且可以分解为 XX^\top（忽略因子 \frac1N），因此 S 的特征值是 X 的奇异值的平方。

更具体地说，X 的奇异值分解（SVD）由下式给出：

(10.47)

其中 U\in \mathbb{R} ^{D\times D} 和 V^\top\in\mathbb{R}^{N\times N} 是正交矩阵，\Sigma\in \mathbb{R}^{D\times N} 是一个矩阵，其非零元素是奇异值 \sigma_i（i\geqslant 0）。由此可得

(10.48)

根据第 4.5 节的结果，我们得到 U 的列是 XX^\top（因此也是 S）的特征向量。此外，S 的特征值 \lambda_d 与 X 的奇异值之间的关系为

(10.49)

S 的特征值与 X 的奇异值之间的这种关系，将最大方差观点（第 10.2 节）与奇异值分解联系起来。

10.4.1 使用低秩矩阵近似的PCA

为了最大化投影数据的方差（或最小化平均平方重建误差），PCA选择在（10.48）中的U的列作为与数据协方差矩阵S的M个最大特征值相关联的特征向量，这样我们就可以将U识别为（10.3）中的投影矩阵B，它将原始数据投影到维度为M的低维子空间上。Eckart-Young定理（第4.6节中的定理4.25）提供了一种直接估计低维表示的方法。考虑最佳秩-M近似

(10.50)

其中X的\|\cdot\|_2是在（4.93）中定义的谱范数。Eckart-Young定理指出，\tilde{X}_M是通过在SVD中截断前M个奇异值得到的。换句话说，我们得到

(10.51)

其中，U_M:=[u_1,\ldots,u_M]\in\mathbb{R}^{D\times M}和V_M:=[\boldsymbol{v}_1,\ldots,\boldsymbol{v}_M]\in\mathbb{R}^{N\times M}是正交矩阵，\boldsymbol\Sigma_M\in\mathbb{R}^{M\times M}是对角矩阵，其对角线上的元素是X的M个最大奇异值。

10.4.2 实际应用方面

寻找特征值和特征向量在其他需要矩阵分解的基础机器学习方法中也非常重要。在理论上，正如我们在第4.2节中讨论的那样，我们可以将特征值作为特征多项式的根来求解。然而，对于大于4\times4的矩阵，这是不可能的，因为我们需要找到5次或更高次多项式的根。然而， Abel -鲁菲尼定理（Ruffini, 1799; Abel, 1826）指出，对于5次或更高次的多项式，这个问题不存在代数解。因此，在实际应用中，我们使用迭代方法来求解特征值或奇异值，这些方法在所有现代线性代数包中都有实现。

在许多应用（如本章介绍的PCA）中，我们只需要少数几个特征向量。计算完整的分解然后丢弃所有特征值不在前几位的特征向量将是浪费的。事实证明，如果我们只对前几个特征向量（具有最大的特征值）感兴趣，那么直接优化这些特征向量的迭代过程在计算上比完整的特征分解（或SVD）更高效。在只需要第一个特征向量的极端情况下，一种称为幂迭代的简单方法非常有效。幂迭代选择一个不在S的零空间中的随机向量x_0，并遵循迭代

(10.52)

这意味着在每个迭代中，向量x_k都与S相乘，然后进行归一化，即我们始终有\|x_k\|=1。这个向量序列收敛到与S的最大特征值相关联的特征向量。原始的Google PageRank算法（Page等，1999）就使用了这样的算法来根据网页的超链接对它们进行排名。