考虑一组观测数据集$\{x_n\}$，其中$n = 1,...,N$，因此$x_n$是一个$D$维欧几里得空间中的变量。 我们的目标是将数据投影到维度$M < D$的空间中，同时最大化投影数据的方差。现阶段，我们假设$M$的值是给定的。稍后在本章中，我们会研究从数据中确定合适的$M$值的方法。

首先，考虑在一维空间$(M = 1)$上的投影。我们可以使用$D$维向量$u_1$定义这个空间的方向。为了方便（并且不失一般性），我们假定选择一个单位向量，从而$u_1^Tu_1 = 1$（注意，我们只对$u_1$的方向感兴趣，而对$u_1$本身的大小不感兴趣）。这样，每个数据点$x_n$被投影到一个标量值$u_1^Tx_n$上。投影数据的均值是$u_1^T\bar{x}$，其中，$\bar{x}$是样本集合的均值，形式为

$$\bar{x} = \frac{1}{N}\sum\limits_{n=1}^Nx_n \tag{12.1}$$

投影数据的方差为

$$\frac{1}{N}\sum\limits_{n=1}^N\{u_1^Tx_n - t_1^T\bar{x}\}^2 = u_1^TSu_1 \tag{12.2}$$

其中$S$是数据的协方差矩阵，定义为

$$S = \frac{1}{N}\sum\limits_{n=1}^N(x_n - \bar{x})(x_n - \bar{x})^T \tag{12.3}$$

我们现在关于$u_1$最大化投影方差$u_1^TSu_1$。很明显，最大化的过程必须满足一定的限制来防止$\Vert u_1 \Vert \to \infty$。恰当的限制来自标准化条件$u_1^Tu_1 = 1$。为了强制满足这个限制，我们引入拉格 朗日乘数，记作$\lambda_1$，然后对下式进行一个无限制的最大化

$$u_1^TSu_1 + \lambda_1(1 - u_1^Tu_1) \tag{12.4}$$

通过令它关于$u_1$的导数等于0，我们看到驻点满足

$$Su_1 = \lambda_1u_1 \tag{12.5}$$

这表明$u_1$一定是$S$的一个特征向量。如果我们左乘$u_1^T$，使用$u_1^Tu_1 = 1$，我们看到方差为

$$u_1^TSu_1 = \lambda_1 \tag{12.6}$$

因此当我们将$u_1$设置为与具有最大的特征值$\lambda_1$的特征向量相等时，方差会达到最大值。这个特 征向量被称为第一主成分。

我们可以用一种增量的方式定义额外的主成分，方法为：在所有与那些已经考虑过的方向正交的所有可能的方向中，将新的方向选择为最大化投影方差的方向。如果我们考虑$M$维投影空间的一般情形，那么最大化投影数据方差的最优线性投影由数据协方差矩阵$S$的$M$个特征向量$u_1,...,u_M$定义，对应于$M$个最大的特征值$\lambda_1,...,\lambda_M$。可以通过归纳法很容易地证明出 来。

总结一下，主成分分析涉及到计算数据集的均值$\bar{x} ̄$和协方差矩阵$S$，然后寻找$S$的对应于$M$个最大特征值的$M$个特征向量。寻找特征值和特征向量的算法以及与特征向量分解相关的定理，可以参考Golub and Van Loan(1996)。注意，计算一个$D \times D$矩阵的完整的特征向量分解的代价为$O(D^3)$。如果我们计划将我们的数据投影到前$M$个主成分中，那么我们只需寻找前$M$个特征值和特征向量。这可以使用更高效的方法得到，例如幂方法（power method）（Golub and Van Loan, 1996），它的时间复杂度为$O(MD^2)$，或我们也可以使用EM算法。