主成分分析

原理

主成分分析（PCA）是一种数据降维算法。设在$n$维空间中的$m$个样本，记作$X=[x^{(1)},x^{(2)},...,x^{(m)}]$，现在对其进行压缩，投影到$k$维空间中，$k<n$，要求损失的信息最少。设$W=[w^{(1)},w^{(2)},...,w^{(k)}]$是此$k$维空间的一组标准正交基，其中$w^{(i)}\in R^n$，满足：$\|w^{(i)}\|_2=1$，$(w^{(i)})^Tw^{(j)}=0（i\ne j）$，设$X$在投影空间中的矩阵表示为$Z$，即有：

$$X_{n\times m}=W_{n\times k}·Z_{k\times m}$$

主成分分析（PCA）是一种数据降维算法。设在$n$维空间中的$m$个样本，记作$X=[x^{(1)},x^{(2)},...,x^{(m)}]$，现在对其进行压缩，投影到$k$维空间中，$k<n$，要求损失的信息最少。设$W=[w^{(1)},w^{(2)},...,w^{(k)}]$是此$k$维空间的一组标准正交基，其中$w^{(i)}\in R^n$，满足：$\|w^{(i)}\|_2=1$，$(w^{(i)})^Tw^{(j)}=0（i\ne j）$，设$X$在投影空间中的矩阵表示为$Z$，即有：$X_{n\times m}=W_{n\times k}·Z_{k\times m}$

显然$Z=W^TX$（根据正交阵性质：$W^TW=E$，即$W^{-1}=W^T$），再将$X$投影在$k$维空间中的矩阵$Z$重新映射回原$n$维空间，重构$X$，得到$X^*=WZ=WW^TX$，既然要使前后损失的信息最少，一种合理的设想是重构后的$X^*$与原始$X$之间的“距离”最小，于是可转化为求解以下最优化问题：

$$\min\limits_W||X-X^*||_F^2=\min\limits_W||X-WW^TX||_F^2 \\\\ s.t. W^TW=E$$

显然$Z=W^TX$（根据正交阵性质：$W^TW=E$，即$W^{-1}=W^T$），再将$X$投影在$k$维空间中的矩阵$Z$重新映射回原$n$维空间，重构$X$，得到$X^*=WZ=WW^TX$，既然要使前后损失的信息最少，一种合理的设想是重构后的$X^*$与原始$X$之间的“距离”最小，于是可转化为求解最优化问题：$\min\limits_W\|X-X^*\|_F^2=\min\limits_W\|X-WW^TX\|_F^2,\,$$s.t. W^TW=E$

化简上式：$\min\limits_W||X-X^*||_F^2=\min\limits_W tr((X-WW^TX)^T(X-WW^TX))$（根据矩阵F范数和迹的关系：$||A||_F=\sqrt{tr(A^TA)}$）

$=\min\limits_Wtr(X^TX-X^TWW^TX-X^TWW^TX+X^TWW^TWW^TX)$ （和$W$无关的项不会影响最优化结果，因此丢弃$X^TX$）

$=\min\limits_Wtr(-2X^TWW^TX+X^TWW^TX)=\min\limits_Wtr(-X^TWW^TX)=\max\limits_Wtr(X^TWW^TX)$（下面再根据矩阵迹运算的循环不变性：$tr(ABC)=tr(CAB)=tr(BCA)$，调一下序）

化简上式：$\min\limits_W||X-X^*||_F^2=\min\limits_W tr((X-WW^TX)^T(X-WW^TX))$$=\min\limits_Wtr(-2X^TWW^TX+X^TWW^TX)=\max\limits_Wtr(X^TWW^TX)$

$=\max\limits_Wtr(W^TXX^TW)$，最终转换为以下优化问题：

$$\max\limits_Wtr(W^TXX^TW) \\ \tag{1}\\ s.t. W^TW=E$$

$=\max\limits_Wtr(W^TXX^TW)$，最终转换为优化问题：$\max\limits_Wtr(W^TXX^TW),\,$$s.t. W^TW=E$（式$(1)$）

利用拉格朗日乘子法求解上述最优化问题，转为求解以下拉格朗日函数的极值（参考南瓜书）：

$$L(W,\Theta)=tr(W^TXX^TW)+<\Theta,(E-W^TW)>$$

$L(W,\Theta)=tr(W^TXX^TW)$$+<\Theta,(E-W^TW)>$

其中$\Theta\in R^{k\times k}$是拉格朗日乘子矩阵，若将约束条件$W^TW=E$拆分下来看，即同时满足$(w^{(i)})^Tw^{(i)}=1$，$(w^{(i)})^Tw^{(j)}=0（i\ne j）$（只看前者模长为1的条件，后者等于0也就是正交的约束就不管了，至于为何继续阅读就明白了，那么拆解下来的约束条件一共就$k$个，拉格朗日乘子也就只有$k$个），显然$\Theta$是一个对角矩阵，记新的拉格朗日乘子矩阵为$\Lambda$，并设$\Lambda=diag\{\lambda_1,\lambda_2,...,\lambda_k\}$，于是新的拉格朗日函数为：

$$L(W,\Lambda)=tr(W^TXX^TW)+tr(\Lambda^T(E-W^TW))$$

其中$\Theta\in R^{k\times k}$是拉格朗日乘子矩阵，若将约束条件$W^TW=E$拆分下来看，即同时满足$(w^{(i)})^Tw^{(i)}=1$，$(w^{(i)})^Tw^{(j)}=0（i\ne j）$（只看前者模长为1的条件，后者等于0也就是正交的约束就不管了，至于为何继续阅读就明白了，那么拆解下来的约束条件一共就$k$个，拉格朗日乘子也就只有$k$个），显然$\Theta$是一个对角矩阵，记新的拉格朗日乘子矩阵为$\Lambda$，并设$\Lambda=diag\{\lambda_1,\lambda_2,...,\lambda_k\}$，于是新的拉格朗日函数为：$L(W,\Lambda)=tr(W^TXX^TW)$$+tr(\Lambda^T(E-W^TW))$

两端对$W$求偏导，令其为0，得到：$\frac{\partial L(W,\Lambda)}{\partial W}=\frac{\partial tr(W^TXX^TW)}{\partial W}-\frac{\partial tr(\Lambda^TW^TW)}{\partial W}=2XX^TW-2W\Lambda=0$，于是$XX^TW=W\Lambda$

注：求$\frac{\partial tr(W^TXX^TW)}{\partial W}$，迹是标量，即标量对矩阵求导，参考矩阵求导术或维基百科，主要基于以下规则：

$$tr(A\pm B)=tr(A)\pm tr(B) \\\\ tr(A)=tr(A^T) \\\\ tr(ABC)=tr(CAB)=tr(BCA) \\\\ d(AB)=d(A)B+Ad(B) \\\\ d(A^T)=(dA)^T \\\\ d(A\pm B)=d(A)\pm d(B) \\\\ d(tr(A))=tr(d(A)) \\\\$$

于是$d(tr(W^TXX^TW))=tr(d(W^TXX^TW))=tr(d(W^T)XX^TW+W^Td(XX^TW))=tr(d(W^T)XX^TW)+tr(W^Td(XX^TW))=tr(XX^TWd(W^T))+tr(W^TXX^Td(W))$
$=tr((XX^TWd(W^T))^T)+tr(W^TXX^Td(W))$$=tr(d(W)W^TXX^T)$$+tr(W^TXX^Td(W))$$=tr(W^TXX^Td(W))$$+tr(W^TXX^Td(W))$$=tr(2W^TXX^Td(W))$$=tr((2XX^TW)^Td(W))$

设$f=f(x_{1,1},...,x_{1,n},x_{2,1},...,x_{2,n},...,$$x_{m,1},...,x_{m,n})=f(X)$，有$df=\frac{\partial f}{\partial x_{1,1}}dx_{1,1}+...+\frac{\partial f}{\partial x_{m,n}}dx_{m,n}=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}\frac{\partial f}{\partial x_{i,j}}dx_{i,j}=tr((\frac{\partial f}{\partial X})^TdX)$成立，其中

$$X=\left[\begin{array}{cccc}{x_{1,1}} & {x_{1,2}} & {\cdots} & {x_{1,n}} \\ {x_{2,1}} & {x_{2,2}} & {\cdots} & {x_{2,n}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {x_{m,1}} & {x_{m,2}} & {\cdots} & {x_{m,n}}\end{array}\right]$$

设$f=f(x_{1,1},...,x_{1,n},x_{2,1},...,x_{2,n},...,$$x_{m,1},...,x_{m,n})=f(X)$，有$df=\frac{\partial f}{\partial x_{1,1}}dx_{1,1}+...+\frac{\partial f}{\partial x_{m,n}}dx_{m,n}=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{n}\frac{\partial f}{\partial x_{i,j}}dx_{i,j}=tr((\frac{\partial f}{\partial X})^TdX)$成立，其中X=\{x_{i,j}\}_{i\in\{1,...,m\},\,j\in\{1,...,n\}}\inR^{m\times n}

于是立即推，$\frac{\partial tr(W^TXX^TW)}{\partial W}=2XX^TW$

再求$\frac{\partial tr(\Lambda^TW^TW)}{\partial W}$，同上，有
$d(tr(\Lambda^TW^TW))=tr(d(\Lambda^TW^TW))=tr(d(\Lambda^T)W^TW+\Lambda^Td(W^TW))=tr(\Lambda^Td(W^TW))=tr(\Lambda^T(d(W^T)W+W^Td(W)))$
$=tr(\Lambda^Td(W^T)W)$$+tr(\Lambda^TW^Td(W))$$=tr(W^Td(W)\Lambda)$$+tr(\Lambda^TW^Td(W))$$=tr(\Lambda W^Td(W))$$+tr(\Lambda^TW^Td(W))$$=tr(2\Lambda^TW^Td(W))$（其中$\Lambda^T=\Lambda$）

立即推，$\frac{\partial tr(\Lambda^TW^TW)}{\partial W}=2W\Lambda$（注解部分结束）

将$XX^TW=W\Lambda$展开来看，有：

$$XX^Tw^{(i)}=\lambda_i w^{(i)} \tag{2}$$

将$XX^TW=W\Lambda$展开来看，有：$XX^Tw^{(i)}=\lambda_i w^{(i)}$（式$(2)$）

$i\in\{1,2,...,k\}$，显然这是矩阵特征值和特征向量的定义式，事实上$XX^T$是实对称矩阵（$(XX^T)^T=XX^T$），而实对称矩阵的不同特征值所对应的特征向量是相互正交的，即使同一特征值的不同特征向量也可以通过施密特正交化使其变得正交，所以上述仅仅在$(w^{(i)})^Tw^{(i)}=1$限制条件下计算出的$W$可以同时满足限制条件：$(w^{(i)})^Tw^{(j)}=0（i\ne j）$

回代式$(1)$，有：

$$\max\limits_Wtr(W^TXX^TW) \\\\ = \max\limits_W\sum\limits_{i=1}^{k}(w^{(i)})^TXX^Tw^{(i)}\quad \text{注}：XX^T\text{相当于常数} \\\\ = \max\limits_W\sum\limits_{i=1}^{k}(w^{(i)})^T·\lambda_i w^{(i)} \\\\ = \max\limits_W\sum\limits_{i=1}^{k}\lambda_i$$

$\max\limits_Wtr(W^TXX^TW)$$= \max\limits_W\sum\limits_{i=1}^{k}(w^{(i)})^TXX^Tw^{(i)}$$= \max\limits_W\sum\limits_{i=1}^{k}(w^{(i)})^T·\lambda_i w^{(i)}$$= \max\limits_W\sum\limits_{i=1}^{k}\lambda_i$

所以只要使特征值$\lambda_1,\lambda_2,...,\lambda_k$是矩阵$XX^T$的前$k$个最大的特征值即可，此时目标函数$(1)$达到最优，即数据降维后的耗损是最小的。简单来说，计算过程是这样的：首先计算出$XX^T$的特征值，挑出其中最大的前$k$个特征值所对应的特征向量，然后进行单位化以及施密特正交化，最后将这些特征向量按列拼凑即得待求$W$

在实际算法中，首先会对数据进行预处理，使样本的均值变为0，我的理解是，考虑到不同特征之间的数值或数量级存在较大差异，此举可防止数值较小的特征被忽略，此时$XX^T$正是这些特征的协方差矩阵

PCA算法：

输入：样本集$X=\{x^{(1)},x^{(2)},...,x^{(m)}\}$，投影空间维度$k$

过程：

1. 预处理：$x^{(i)}=x^{(i)}-\frac{1}{m}\sum\limits_{j=1}^mx^{(j)}$
2. 计算样本协方差矩阵$XX^T$（此处省略了协方差矩阵前面的常系数，这是因为对一个矩阵做特征分解，$A\xi=\lambda\xi$，两边同乘一个常系数$a$并不影响特征向量的值，$aA\xi=a\lambda\xi=\lambda^{'}\xi$）
3. 对协方差矩阵做特征值分解
4. 取前$k$个最大的特征值以及其对应的特征向量（经过单位化和正交化，简称规范化）：$w^{(1)},w^{(2)},...,w^{(k)}$

输出：$W=[w^{(1)},w^{(2)},...,w^{(k)}]$，于是投影矩阵为$W^T$，有$Z=W^TX$，$Z$是降维后的数据

核PCA

——本节推导参考[1]

对于数据集$X=[x_1,x_2,...,x_m]$，$x_i\in R^n$，现在通过非线性变换$\phi:R^n\rightarrow R^N$将全部样本映射到高维特征空间（希尔伯特空间），设$z_i$是原始空间中的样本点$x_i$在高维空间中的像，有$z_i=\phi(x_i)$，然后在此高维空间（$R^N$）实施PCA，降维到$d$维空间，要做PCA，首先计算协方差矩阵：

$$C=\frac{1}{m}\sum\limits_{i=1}^{m}\left(\phi(x_i)-\frac{1}{m}\sum\limits_{j=1}^{m}\phi(x_j)\right)\left(\phi(x_i)-\frac{1}{m}\sum\limits_{j=1}^{m}\phi(x_j)\right)^T$$

对于数据集$X=[x_1,x_2,...,x_m]$，$x_i\in R^n$，现在通过非线性变换$\phi:R^n\rightarrow R^N$将全部样本映射到高维特征空间（希尔伯特空间），设$z_i$是原始空间中的样本点$x_i$在高维空间中的像，有$z_i=\phi(x_i)$，然后在此高维空间（$R^N$）实施PCA，降维到$d$维空间，要做PCA，首先计算协方差矩阵：$C=\frac{1}{m}\sum\limits_{i=1}^{m}(\phi(x_i)-\frac{1}{m}\sum\limits_{j=1}^{m}\phi(x_j))$$(\phi(x_i)-\frac{1}{m}\sum\limits_{j=1}^{m}\phi(x_j))^T$

为描述方便，令$\psi(x_i)=\phi(x_i)-\frac{1}{m}\sum\limits_{j=1}^{m}\phi(x_j)$，则协方差矩阵$C=\sum\limits_{i=1}^{m}\psi(x_i)\psi(x_i)^T$（此处已省略常系数$\frac{1}{m}$），根据公式$(2)$有$Cv_j=\lambda_jv_j$，$j\in\{1,2,...,d\}$（指取前$d$个最大的特征值$\lambda_j$），其中$v_j$是$C$对应于特征值$\lambda_j$的特征向量，即：

$$(\sum\limits_{i=1}^{m}\psi(x_i)\psi(x_i)^T)v_j=\lambda_jv_j$$

于是$v_j=\sum\limits_{i=1}^{m}\frac{1}{\lambda_j}\psi(x_i)\psi(x_i)^Tv_j$，令$\alpha_i^j=\frac{1}{\lambda_j}\psi(x_i)^Tv_j$，则：

$$v_j=\sum\limits_{i=1}^{m}\psi(x_i)\alpha_i^j$$

为描述方便，令$\psi(x_i)=\phi(x_i)-\frac{1}{m}\sum\limits_{j=1}^{m}\phi(x_j)$，则协方差矩阵$C=\sum\limits_{i=1}^{m}\psi(x_i)\psi(x_i)^T$（此处已省略常系数$\frac{1}{m}$），根据公式$(2)$有$Cv_j=\lambda_jv_j$，$j\in\{1,2,...,d\}$（指取前$d$个最大的特征值$\lambda_j$），其中$v_j$是$C$对应于特征值$\lambda_j$的特征向量，即：$(\sum\limits_{i=1}^{m}\psi(x_i)\psi(x_i)^T)v_j=\lambda_jv_j$，于是$v_j=\sum\limits_{i=1}^{m}\frac{1}{\lambda_j}\psi(x_i)\psi(x_i)^Tv_j$，令$\alpha_i^j=\frac{1}{\lambda_j}\psi(x_i)^Tv_j$，则：$v_j=\sum\limits_{i=1}^{m}\psi(x_i)\alpha_i^j$

在$Cv_j=\lambda_jv_j$两边左乘$\psi(x_k)^T$得到$\psi(x_k)^TCv_j=\psi(x_k)^T\lambda_jv_j$，化简该式：$\text{左式}=\psi(x_k)^T(\sum\limits_{i=1}^m\psi(x_i)\psi(x_i)^T)(\sum\limits_{i=1}^m\psi(x_i)\alpha_i^j)\quad$$（\text{根据}(\sum\limits_{i=1}^mf(x_i))·(\sum\limits_{i=1}^ng(x_i))=\sum\limits_{i=1}^m\sum\limits_{j=1}^n(f(x_i)g(x_j))）\\=\psi(x_k)^T\sum\limits_{i=1}^m\sum\limits_{l=1}^m(\psi(x_i)\psi(x_i)^T·\psi(x_l)\alpha_l^j)=\sum\limits_{i=1}^m\sum\limits_{l=1}^m(\psi(x_k)^T\psi(x_i)\psi(x_i)^T\psi(x_l)·\alpha_l^j)\\=\sum\limits_{i=1}^m([\psi(x_k)^T\psi(x_i)\psi(x_i)^T\psi(x_1),$$\psi(x_k)^T\psi(x_i)\psi(x_i)^T\psi(x_2),...,$$\psi(x_k)^T\psi(x_i)\psi(x_i)^T\psi(x_m)]\begin{bmatrix}\alpha_1^j \\ \alpha_2^j \\.\\.\\.\\ \alpha_m^j\end{bmatrix})\\=[\psi(x_k)^T·(\sum\limits_{i=1}^m\psi(x_i)\psi(x_i)^T)·\psi(x_1),$$\psi(x_k)^T·(\sum\limits_{i=1}^m\psi(x_i)\psi(x_i)^T)·\psi(x_2),...,$$\psi(x_k)^T·(\sum\limits_{i=1}^m\psi(x_i)\psi(x_i)^T)·\psi(x_m)]\begin{bmatrix}\alpha_1^j \\ \alpha_2^j \\.\\.\\.\\ \alpha_m^j\end{bmatrix}\\=\text{右式}=\lambda_j\sum\limits_{i=1}^m(\psi(x_k)^T\psi(x_i)·\alpha_i^j)=\lambda_j[\psi(x_k)^T\psi(x_1),\psi(x_k)^T\psi(x_2),...,$$\psi(x_k)^T\psi(x_m)]\begin{bmatrix}\alpha_1^j \\ \alpha_2^j \\.\\.\\.\\ \alpha_m^j\end{bmatrix}$

在$Cv_j=\lambda_jv_j$两边左乘$\psi(x_k)^T$得到$\psi(x_k)^TCv_j=\psi(x_k)^T\lambda_jv_j$，化简该式：$\text{左式}=[\psi(x_k)^T·(\sum\limits_{i=1}^m\psi(x_i)\psi(x_i)^T)·\psi(x_1),$$\psi(x_k)^T·(\sum\limits_{i=1}^m\psi(x_i)\psi(x_i)^T)·\psi(x_2),...,$$\psi(x_k)^T·(\sum\limits_{i=1}^m\psi(x_i)\psi(x_i)^T)·\psi(x_m)]$$[\alpha_1^j , \alpha_2^j ,... , \alpha_m^j]^T$$=\text{右式}=\lambda_j[\psi(x_k)^T\psi(x_1),\psi(x_k)^T\psi(x_2),...,$$\psi(x_k)^T\psi(x_m)]$$[\alpha_1^j , \alpha_2^j ,... , \alpha_m^j]^T$

其中$k\in \{1,2,...,m\}$，对全部的$k$应用上述等式，拼凑得到：$\overline{K}^2\alpha^j=\lambda_j\overline{K}\alpha^j$（如果正向推有困难，可以反向证明其成立），其中$\overline{K}^2=\overline{K}·\overline{K}$（矩阵乘法），$\overline{K}、\alpha^j$分别为：

$$\overline{K}=\begin{bmatrix}{\psi(x_1)^T\psi(x_1)} & {\psi(x_1)^T\psi(x_2)} & {\cdots} & {\psi(x_1)^T\psi(x_m)} \\ {\psi(x_2)^T\psi(x_1)} & {\psi(x_2)^T\psi(x_2)} & {\cdots} & {\psi(x_2)^T\psi(x_m)} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {\psi(x_m)^T\psi(x_1)} & {\psi(x_m)^T\psi(x_2)} & {\cdots} & {\psi(x_m)^T\psi(x_m)}\end{bmatrix} \\ \alpha^j=[\alpha_1^j,\alpha_2^j,...,\alpha_m^j]^T$$

$\overline{K}=\{\psi(x_i)^T\psi(x_j)\}_{i,j\in\{1,...,m\}}\in R^{m\times m},\,$$\alpha^j=[\alpha_1^j,\alpha_2^j,...,\alpha_m^j]^T$

于是有：

$$\overline{K}\alpha^j=\lambda_j\alpha^j \tag{3}$$

于是有：$\overline{K}\alpha^j=\lambda_j\alpha^j$（式$(3)$）

$j\in\{1,2,...,d\}$，显然，式$(3)$就是一个特征值分解问题（并取$\overline{K}$前$d$个最大的特征值所对应的特征向量），现在要计算$\overline{K}$

$\overline{K}_{i,j}=\psi(x_i)^T\psi(x_j)=\left(\phi(x_i)-\frac{1}{m}\sum\limits_{l=1}^{m}\phi(x_l)\right)^T$$\left(\phi(x_j)-\frac{1}{m}\sum\limits_{l=1}^{m}\phi(x_l)\right)$$=\left(\phi(x_i)^T-\frac{1}{m}\sum\limits_{l=1}^m\phi(x_l)^T\right)$$\left(\phi(x_j)-\frac{1}{m}\sum\limits_{l=1}^{m}\phi(x_l)\right) \\=\phi(x_i)^T\phi(x_j)-\frac{1}{m}\phi(x_i)^T(\sum\limits_{l=1}^m\phi(x_l))-\frac{1}{m}(\sum\limits_{l=1}^m\phi(x_l)^T)\phi(x_j)+\frac{1}{m^2}(\sum\limits_{l=1}^m\phi(x_l)^T)(\sum\limits_{l=1}^m\phi(x_l))$

$\overline{K}_{i,j}=\psi(x_i)^T\psi(x_j)=(\phi(x_i)-\frac{1}{m}\sum\limits_{l=1}^{m}\phi(x_l))^T$$(\phi(x_j)-\frac{1}{m}\sum\limits_{l=1}^{m}\phi(x_l))$$=(\phi(x_i)^T-\frac{1}{m}\sum\limits_{l=1}^m\phi(x_l)^T)$$(\phi(x_j)-\frac{1}{m}\sum\limits_{l=1}^{m}\phi(x_l))$$=\phi(x_i)^T\phi(x_j)-\frac{1}{m}\phi(x_i)^T(\sum\limits_{l=1}^m\phi(x_l))-\frac{1}{m}(\sum\limits_{l=1}^m\phi(x_l)^T)\phi(x_j)+\frac{1}{m^2}(\sum\limits_{l=1}^m\phi(x_l)^T)(\sum\limits_{l=1}^m\phi(x_l))$

引入核函数$\mathbf{k}(·,·)$：

$$\mathbf{k}(x_i,x_j)=\phi(x_i)^T\phi(x_j)$$

引入核函数$\mathbf{k}(·,·)$：$\mathbf{k}(x_i,x_j)=\phi(x_i)^T\phi(x_j)$

其对应的核矩阵为：

$$K=\begin{bmatrix}{\mathbf{k}(x_1,x_1)} & {\mathbf{k}(x_1,x_2)} & {\cdots} & {\mathbf{k}(x_1,x_m)} \\ {\mathbf{k}(x_2,x_1)} & {\mathbf{k}(x_2,x_2)} & {\cdots} & {\mathbf{k}(x_2,x_m)} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {\mathbf{k}(x_m,x_1)} & {\mathbf{k}(x_m,x_2)} & {\cdots} & {\mathbf{k}(x_m,x_m)}\end{bmatrix} \tag{4}$$

其对应的核矩阵为：$K=\{\mathbf{k}(x_i,x_j)\}_{i,j\in\{1,...,m\}} \in R^{m\times m}$（式$(4)$）

对$\overline{K}_{i,j}$继续化简得到$\overline{K}_{i,j}=K_{i,j}-\frac{1}{m}\sum\limits_{l=1}^m(\phi(x_i)^T\phi(x_l))-\frac{1}{m}\sum\limits_{l=1}^m(\phi(x_l)^T\phi(x_j))+\frac{1}{m^2}\sum\limits_{l=1}^m\sum\limits_{p=1}^m(\phi(x_l)^T\phi(x_p))$$=K_{i,j}-\frac{1}{m}\sum\limits_{l=1}^mK_{i,l}-\frac{1}{m}\sum\limits_{l=1}^mK_{l,j}+\frac{1}{m^2}\sum\limits_{l=1}^m\sum\limits_{p=1}^mK_{l,p}$

于是有（如果看不懂，可以反向证明其成立）：

$$\overline{K}=K-KI_m-I_mK+I_mKI_m \tag{5}$$

于是有（如果看不懂，可以反向证明其成立）：$\overline{K}=K-KI_m-I_mK+I_mKI_m$（式$(5)$）

其中$I$是元素全为1的$m\times m$形矩阵，$I_m$表示$\frac{1}{m}I$。$\overline{K}$求出来了，$\alpha^j$也就解出来了，于是$v_j=\sum\limits_{i=1}^m\psi(x_i)\alpha_i^j=\psi(X)\alpha^j$，其中$\psi(X)=[\psi(x_1),\psi(x_2),...,\psi(x_m)]$，根据之前的PCA算法可知，$v_j$需要进行单位化和正交化（？），然而$v_j$实际是算不出来的，但是可以修改$\alpha^j$的值使满足$\|v_j\|=1$的条件，根据$\|v_j\|^2=v_j^Tv_j=(\alpha^j)^T\psi(X)^T\psi(X)\alpha^j=(\alpha^j)^T\overline{K}\alpha^j=\lambda_j(\alpha^j)^T\alpha^j=1$，从而得到新的$\alpha^j$值（$j\in \{1,2,...,d\}$）。现在给定原始空间中的样本$x_i$，可以计算其在KPCA投影空间中的表示$V^T\psi(x_i)$（先将$x_i$映射到高维空间得到$\psi(x_i)$，再从高维希尔伯特空间做PCA降维，即左乘投影矩阵$V^T$），其中$V=[v_1,v_2,...,v_d]=\psi(X)[\alpha^1,\alpha^2,...,\alpha^d]$，有$V^T\psi(x_i)=\begin{bmatrix}(\alpha^1)^T\\\vdots\\(\alpha^d)^T\end{bmatrix}\psi(X)^T\psi(x_i)=\begin{bmatrix}(\alpha^1)^T\\\vdots\\(\alpha^d)^T\end{bmatrix}\begin{bmatrix}\psi(x_1)^T\\\vdots\\\psi(x_m)^T\end{bmatrix}\psi(x_i)=\begin{bmatrix}(\alpha^1)^T\\\vdots\\(\alpha^d)^T\end{bmatrix}_{d\times m}\begin{bmatrix}\psi(x_1)^T\psi(x_i)\\\vdots\\\psi(x_m)^T\psi(x_i)\end{bmatrix}_{m\times 1}=\begin{bmatrix}(\alpha^1)^T\\\vdots\\(\alpha^d)^T\end{bmatrix}K_{:,i}\in R^d$

其中$I$是元素全为1的$m\times m$形矩阵，$I_m$表示$\frac{1}{m}I$。$\overline{K}$求出来了，$\alpha^j$也就解出来了，于是$v_j=\sum\limits_{i=1}^m\psi(x_i)\alpha_i^j=\psi(X)\alpha^j$，其中$\psi(X)=[\psi(x_1),\psi(x_2),...,\psi(x_m)]$，根据之前的PCA算法可知，$v_j$需要进行单位化和正交化（？），然而$v_j$实际是算不出来的，但是可以修改$\alpha^j$的值使满足$\|v_j\|=1$的条件，根据$\|v_j\|^2=v_j^Tv_j=(\alpha^j)^T\psi(X)^T\psi(X)\alpha^j=(\alpha^j)^T\overline{K}\alpha^j=\lambda_j(\alpha^j)^T\alpha^j=1$，从而得到新的$\alpha^j$值（$j\in \{1,2,...,d\}$）。现在给定原始空间中的样本$x_i$，可以计算其在KPCA投影空间中的表示$V^T\psi(x_i)$（先将$x_i$映射到高维空间得到$\psi(x_i)$，再从高维希尔伯特空间做PCA降维，即左乘投影矩阵$V^T$），其中$V=[v_1,v_2,...,v_d]=\psi(X)[\alpha^1,\alpha^2,...,\alpha^d]$，有$V^T\psi(x_i)=[\alpha^1,...,\alpha^d]^T[\psi(x_1),...,\psi(x_m)]^T\psi(x_i)=[\alpha^1,...,\alpha^d]^T_{d\times m}(K_{:,i})_{m\times 1}\in R^d$

注：推荐李振轩老师的视频教程，其从“什么样的投影轴可以最大化投影后的样本方差，以使得投影后的样本分散得最开（显然如果投影到同一个点意味着信息将全部丢失，所以投影后的点离散程度越大越好）”的视角来看待PCA问题，而且推导形式更简单，可以参见我做的笔记[3]

[1] 核主成分分析
[2] 协方差矩阵
[3] 线性判别分析·李振轩笔记