线代基础
在简单的直角坐标系中，如果我们规定 \vec{a}_1 = (1, 0)，\vec{a}_2 = (0, 1) 这两个基底，则任何一个向量 \vec{A} 都可以表示成 x\cdot\vec{a}_1+y\cdot\vec{a}_2 这样的形式，我们在这个等式两边同时乘上 \vec{a}_1 得到：
\vec{A}\cdot\vec{a}_1=x\cdot\vec{a}_1\cdot\vec{a}_1+y\cdot\vec{a}_2\cdot\vec{a}_1
$$
由于 \vec{a}_1 和 \vec{a}_2 正交且 \vec{a}_1 的长度为1，故公式可化为：
\vec{A}\cdot\vec{a}_1=x
$$
这个公式的适用范围很广，单位向量可以拓展到多维，单位向量的方向也可以是我们指定的任意方向，那么我们就可以得到，任一向量在某一方向上投影的长度等于其与该方向上单位向量点积后的值。
点积在线代中有一个非常方便的表示方式，本文我们规定所有的向量默认都是列向量，那么
\vec{a} \cdot \vec{b} = \vec{a}^{\,\top} \vec{b}
$$
这样写的好处就是我们可以方便的写出多个向量在多个方向上面投影的值，例如
\begin{pmatrix} 1 & 0 & 0 \\ 0 & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix} \begin{pmatrix} 1 & 2 & 1\\ 1 & 0 & 2\\ 0 & 2 & 3 \end{pmatrix}= \begin{pmatrix} 1 & 2 & 1\\ \frac{\sqrt{2}}{2} & \sqrt{2} & \frac{5\sqrt{2}}{2} \end{pmatrix}
$$
表示的就是在三维空间上 (1 ,1,0)^T ，(2,0,2)^T，(1, 2, 3)^T三个向量，在(1 ,0,0)^T，(0 ,\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2})^T 这两个三维方向上的投影。如果我们把每个向量用一个字母表示，那么它的含义会更加清晰。p_1，p_2表示单位基向量，a_1，a_2，a_3是列向量，那么通用的表示方式为：
\begin{pmatrix} p_1 \\ p_2 \end{pmatrix} \begin{pmatrix} a_1 & a_2& a_3 \end{pmatrix}= \begin{pmatrix} p_1a_1 &p_1a_2&p_1a_3\\ p_2a_1&p_2a_2&p_2a_3 \end{pmatrix}
$$
所以在这里两个矩阵相乘的意义是将右边矩阵的每一列求出其左边矩阵的每一行为基的投影的值。
最大可分性
PCA叫做主成分分析，它的目的是将一组原本维度较高的向量 X 按照某种方式降到低维度，提取出该向量的主要内容。它是个线性映射，由上一节的推导可知其可以表示成线代中左乘一个行数很小（基数少），列数为 X 的矩阵。我们可以在这里规定这个矩阵的每一行就是该n维空间的一个基向量（这样规定可以使我们能够公平的比较不同方向上的方差的差异）。
如果这组 X 在该向量上的投影都集中在大致一个区域（方差很小），那么可以认为 X 在该方向上的内容比较相似，丢失了较多的信息，相反如果方差很大那么我们就保留了 X 中的较多的信息。就像是尽可能多提取了 X 这组向量中的差异，并且避免去提取共性，因为差异总是蕴含这更多的信息。这就是PCA的一个优化角度——最大可分性，另一个角度是最小重构性，简言之就是在一个超空间选择一个平面或是超平面，使得分布在这个超空间的点都（ X 的坐标）离这个平面比较近。本文是从最大可分性来证明PCA的公式的。
方差
方差也可表示为：
Var(x)=\frac{1}{m}\sum_{i=1}^{m}(x_i-\mu)^2
$$
严格来说无偏估计的分母应该是 m-1，但为了推导简洁，本文统一使用 m，不影响最终结论。 这里我们将均值化为0，故方差可以化为如下的平方和形式
Var(x)=\frac{1}{m}\sum_{i=1}^{m}x_i^2
$$
我们的优化目标就变为找到一个基向量使得所有数据在其上的投影的方差最大。
协方差
如果我们要将维度降到大于等于二维，那么为了使不同维度之间保存的信息不重复，我们需要用到协方差。协方差衡量的是两个变量之间的相关性，大于零是正相关，等于零是线性无关，公式如下：
Cov(x,y)=\frac{1}{m}\sum_{i=1}^{m}(x_i-\mu_x)(y_i-\mu_y)
$$
可化为：
Cov(x,y)=\frac{1}{m}\sum_{i=1}^{m}x_iy_i
$$
协方差的优化目标是使我们 n 个基向量上的投影彼此之间的协方差为0。
协方差矩阵
在线性代数中协方差矩阵定义为 \frac{1}{m}XX^T ，其中 X 为多个列向量转置后一行行摆放，公式为：
\frac{1}{m} \begin{pmatrix} x_1^T \\ x_2^T \end{pmatrix} \begin{pmatrix} x_1 & x_2 \end{pmatrix}= \begin{pmatrix} Cov(x_1, x_1) & Cov(x_1, x_2) \\ Cov(x_2, x_1) & Cov(x_2, x_2) \end{pmatrix}
$$
我们可以发现矩阵对角线上的元素就是数据每一维的方差，不在对角线上的元素是不同维度的协方差，由于 Cov(x_1, x_2)=Cov(x_2, x_1) 所以该矩阵还是一个对称矩阵。
矩阵对角化
假定我们对于原始数据有一个线性变换 P ，假设原始数据的协方差矩阵为 C 那么得到的协方差矩阵 D 可以做如下的推导：
\begin{aligned} D&=\frac{1}{m}(PX)(PX)^T\\ &=\frac{1}{m}PXX^TP^T\\ &=PCP^T \end{aligned}
$$
我们的目标是将X在我们需要的前k个方向上投影的方差尽可能的大，协方差保证为零，现在我们需要找到一个 P 使得 D 能够满足这两点要求。而碰巧的是，每一个实对称矩阵都可以刚好通过一个形如 PCP^T 的形式去化成一个对角矩阵。
上述结论等价于所有实对称矩阵都有n个（n为对称矩阵的维度）两两垂直的特征向量，为什么等价于这个结论呢？因为特征值的基本性质，特征值的定义是一个矩阵乘上某一个特征向量后，该特征向量的方向不变而其大小变为原来的特征值倍（这里的大小可以为负，指的就是该特征向量的反方向），公式为：
C\vec{p}_1=\lambda_1\vec{p}_1
$$
将等式的左右两边同时转置，那么等式就会变成
\vec{p}_1^TC^T=\vec{p}_1^TC=\lambda_1\vec{p}_1^T
$$
假设 P 为n个彼此正交的特征向量按行摆放，则n个特征值堆叠起来得到
PC=\begin{pmatrix} \vec{p}_1^T\\ \vec{p}_2^T\\ \vdots\\ \vec{p}_n^T \end{pmatrix} C= \begin{pmatrix} \lambda_1\vec{p}_1^T\\ \lambda_2\vec{p}_2^T\\ \vdots\\ \lambda_n\vec{p}_n^T \end{pmatrix}=\Lambda P
$$
其中 \Lambda 为对角矩阵每一行的对角元素对应 P 每一行特征向量对应的特征值。那么
PCP^T=\Lambda PP^T=\Lambda
$$
\Lambda 为对角矩阵每一行的对角元素对应 P 每一行特征向量对应的特征值。
而要证明所有实对称矩阵都有n个两两垂直的特征向量，就需要证明实对称矩阵的两个性质
性质一：实对称矩阵不同的特征值对应的特征向量两两垂直
假设有 C 两个不同的特征向量 \vec{p}_1，\vec{p}_2 ，那么
\vec{p}_1^TC\vec{p}_2=\vec{p}_1^T(\lambda_2\vec{p}_2)=\lambda_2\vec{p}_1^T\vec{p}_2
$$
也等于
\vec{p}_1^TC\vec{p}_2=(C\vec{p}_1)^T\vec{p}_2=\lambda_1\vec{p}_1^T\vec{p}_2
$$
因为 \lambda_1 不等于 \lambda_2 所以 \vec{p}_1，\vec{p}_2 必定正交即垂直。
性质二：实对称矩阵每个特征值对应的代数重数等于几何重数
证明性质2首先要用到实对称矩阵的特征值都是实数，下面给出推导：
设 C\vec{v} = \lambda\vec{v}，对两边取共轭并转置，利用 \overline{C} = C（实矩阵）和 C^{\top} = C（对称），得到：
\bar{\vec{v}}^{\top} C = \bar{\lambda} \bar{\vec{v}}^{\top}
$$
右乘 \vec{v} 得到：
\bar{\vec{v}}^{\top} C \vec{v} = \bar{\lambda} \bar{\vec{v}}^{\top} \vec{v}
$$
另一方面，直接从 C\vec{v} = \lambda\vec{v} 左乘 \bar{\vec{v}}^{\top}：
\bar{\vec{v}}^{\top} C \vec{v} = \lambda \bar{\vec{v}}^{\top} \vec{v}
$$
两式相减：
(\bar{\lambda} - \lambda)\bar{\vec{v}}^{\top}\vec{v} = 0
$$
由于 \bar{\vec{v}}^{\top}\vec{v} = \sum|v_i|^2 > 0，所以 \bar{\lambda} = \lambda，即 \lambda 是实数。
然后我们用归纳法来证明性质2
归纳基础：n = 1 时，C 就是一个实数，任何非零实数都是它的特征向量，结论显然成立。
归纳假设：假设对所有 n-1 阶实对称矩阵，结论成立。
归纳步骤：现在证明 n 阶的情况。
第一步：找到第一个特征向量
由前面的证明，实对称矩阵的特征值都是实数。而 n 阶矩阵的特征方程 \det(C - \lambda I) = 0 是一个 n 次多项式，至少有一个实根 \lambda_1（因为所有根都是实数）。对应地，至少存在一个单位特征向量 \vec{p}_1，满足：
C\vec{p}_1 = \lambda_1 \vec{p}_1
$$
第二步：构造正交矩阵 Q
以 \vec{p}_1 为第一列，再从 \vec{p}_1 的正交补空间中取 n-1 个标准正交向量（可通过 Gram-Schmidt 正交化得到），拼成一个 n \times n 的正交矩阵：
Q = \begin{pmatrix} \vec{p}_1 & \vec{q}_2 & \cdots & \vec{q}_n \end{pmatrix}
$$
其中 \vec{q}_2, \ldots, \vec{q}_n 两两正交，且都与 \vec{p}_1 正交。
第三步：用 Q 对 C 做相似变换
计算 Q^{\top}CQ：
Q^{\top}CQ=(C^TQ)^TQ=(CQ)^TQ
$$
因为 CQ 中的第一列为 \lambda_1 \vec{p}_1 ，所以转置后的 (CQ)^T 第一行为 \lambda_1 \vec{p}_1 ，有因为 \vec{q}_2, \ldots, \vec{q}_n 都与 \vec{p}_1 正交，故 Q^{\top}CQ 的第一行是是 (\lambda_1, 0, \ldots, 0)。
又因为 C 对称，Q 正交，所以 Q^{\top}CQ 也是对称矩阵。第一列的第 2 到第 n 个元素都是 0，那么由对称性，第一行的第 2 到第 n 个元素也必须是 0。所以：
Q^{\top}CQ = \begin{pmatrix} \lambda_1 & \vec{0}^{\top} \\ \vec{0} & C' \end{pmatrix}
$$
第四步：对 C' 使用归纳假设
C' 是一个 (n-1) \times (n-1) 的矩阵。由于 Q^{\top}CQ 整体是实对称的，右下角的 C' 也是实对称的。
由归纳假设，C' 有 n-1 个两两正交的单位特征向量 \vec{e}_2', \ldots, \vec{e}_n'，对应特征值 \lambda_2, \ldots, \lambda_n。
第五步：变换回原空间
对 C' 的每个特征向量 \vec{e}_i'（(n-1) 维），在前面补一个 0 变成 n 维：
\vec{e}_i = \begin{pmatrix} 0 \\ \vec{e}_i' \end{pmatrix}
$$
那么 \vec{e}_i 是 Q^{\top}CQ 的特征向量（因为右上和左下都是零，\lambda_1 那行不受影响）。
再通过 Q 变换回原空间：\vec{p}_i = Q\vec{e}_i，就得到 C 的特征向量：
C(Q\vec{e}_i) = Q(Q^{\top}CQ)\vec{e}_i = Q(\lambda_i \vec{e}_i) = \lambda_i(Q\vec{e}_i)
$$
由于 Q 是正交矩阵，正交变换保持内积不变，所以 \vec{e}_2, \ldots, \vec{e}_n 两两正交意味着 Q\vec{e}_2, \ldots, Q\vec{e}_n 也两两正交。再加上 \vec{p}_1 = Q\vec{e}_1（其中 \vec{e}_1 = (1, 0, \ldots, 0)^{\top}），它与其余所有 Q\vec{e}_i 也正交。
最终我们得到了 C 的 n 个两两正交的特征向量：\vec{p}_1, Q\vec{e}_2, \ldots, Q\vec{e}_n。
求解步骤
1.将数据矩阵减去他们每一列的矩阵 2.求改矩阵的的协方差矩阵 3.求该协方差矩阵的特征值及其对应的特征向量