PCA降维算法详细推导

关于一个小小的PCA的推导

如果有概念不懂，请从目录中查找，或者直接检索。
如果想直入主题，请从第7小节开始看。

1 谱分解 (spectral decomposition)

矩阵中有一个概念叫做谱分解。

定理2.5.3

所以根据定理2.5.3的(a)(b)可知：**正规矩阵(请看第12条）都是酉可对角化（unitarily diagonalizable)**的，形式为：存在一个酉矩阵V使得A =$V\Lambda V^{\ast }$, 并且$\Lambda =diag({\lambda }_1,\dots ,{\lambda }_n)$.

定理2.2.2 酉相似的两个矩阵的元素平方和相等。

由于酉相似的两个矩阵的元素平方和相等，所以自然就可以得到性质c.

根据舒尔三角化定理，任何复方阵都酉相似于一个三角阵，该三角阵的对角元素为其特征值。则写出它的舒尔分解形式：

$A=UT{U}^{\ast }$, 其中$U=[u_1,\dots ,u_n]$是一个酉矩阵，$T=[t_{ij}]\in M_n$是一个上三角矩阵。这样一个分解可以写成AU = UT，即A$[u_1,\dots ,u_n]$ =$[u_1,\dots ,u_n]$T, 而T是对角阵，所以$Au_i = t_{ii}u_i $ for each $i=1,\dots ,n$, 因此$U$的n个列是A的标准正交的特征向量。

根据矩阵分析第134页首次出现谱分解给出的定义来看，谱分解的定义可以这么写：

其中酉矩阵的n个列向量就是A的特征向量。

一个正规矩阵可以表示成一个酉矩阵、一个对角矩阵、以及该酉矩阵的共轭转置的乘积。这样一个分解称作该正规矩阵的谱分解。

谱分解中对角矩阵的对角元便是其特征值，酉矩阵的列向量便是其对应的特征向量。

2 奇异矩阵(singular matrix)

一个线性变换或者矩阵被称之为nonsingular(非奇异)（不奇怪），如果这个变换仅对0这个输入产生0的输出，否则它就是被称作singular(奇异)

对于这个概念，我觉得很有意思。singular这个英文单词百度百科上的英文意思是：奇怪的，独特的，独一无二的。根据上面的定义，如果某个变换将一个非零的东西映射成了0，则这个变换是很奇怪的，是异常的。

我觉得称之为非比寻常也是可以的，说明这样的变换具有一种超能力，能将非零的东西变成零，以至于独孤求败，无人可比（如果它是方阵，则没有与之对应的逆矩阵）。

方阵中，哪些矩阵不平常呢？

如果A是一个方阵，则下列条件是等价的。

A是非奇异矩阵, 等价于该矩阵存在逆矩阵 ，

等价于 Ax =0的有唯一解零向量 ，

等价于 0肯定不是A的特征值（因为矩阵的特征值的定义中需要从非零向量映射，而非奇异矩阵无法将非零向量映射到零向量，故0断然不是A的一个特征值）

3 酉相似(unitary similarity)

定义：对于酉矩阵来说，酉矩阵的共轭转置即为其逆矩阵。所以存在一个相似变换其对应的矩阵为酉矩阵，则称变换前后的两个矩阵是酉相似的。

性质：

• 如果两个矩阵酉相似，则两个矩阵的元素平方和相等，即二者的共轭转置与原矩阵的乘积的迹相等。$\mathrm{tr}{B}^{\ast }B=\mathrm{tr}{A}^{\ast }A$

• 如果某个矩阵酉相似于一个对角矩阵，则称该矩阵是酉可对角化的。

舒尔定理

可能基本矩阵理论中最有用的一个事实要归于舒尔的一个定理：任何复方阵都酉相似于一个三角阵，该三角阵的对角元素是矩阵的特征值，可以以任意特定的顺序排列。这就是大名鼎鼎的舒尔形式、舒尔三角化：任何一个方阵都酉相似于一个对角线元素为该方阵的特征值的上三角矩阵。

4 酉矩阵

定义：酉矩阵的逆矩阵是其共轭转置。

说明：酉矩阵这一类矩阵的逆矩阵的形式简单，就是其共轭转置。求共轭转置比求逆更加简单。

性质：

• 酉矩阵是非奇异矩阵，其逆矩阵就是其共轭转置。酉矩阵的行向量组和列向量组均是标准正交的。酉矩阵这个线性变换对向量是保持距离的，即向量$x$和向量$Ux$有相同的欧式范数。
• 两个酉矩阵的乘积（如果可以相乘）仍为酉矩阵。

5 共轭变换

通过一个非奇异矩阵以及它的共轭转置来对一个矩阵进行映射，这样的变换称作共轭变换，形如：$A\to S^{\ast }AS$

6 酉等价

定义：将一个矩阵，通过两个酉矩阵变换到一个新的矩阵，这样一个变换称作酉等价。

性质：

• 每一个矩阵均酉等价于一个非负的对角阵，该对角阵的元素为矩阵的奇异值。这些奇异值很重要。

7 矩阵的迹的计算以及PCA算法推导

在矩阵理论推导过程中，经常会使用到矩阵的迹的计算方法，所以掌握该类计算方法对于理论推导是大有裨益的。

设$B\in {\mathbb{R}}^{d,n}$ ,$D\in {\mathbb{R}}^{d,d}$, 求$B^{T}DB$的迹。

用到的一个技术叫做 分块矩阵中的列分块。

（将矩阵进行分块，可以简化计算。当然在分块计算时，要先检查矩阵的行数与列数，判断是否可以进行相乘）

这里需要补充分块矩阵的相关知识。

https://baike.baidu.com/item/%E5%88%86%E5%9D%97%E7%9F%A9%E9%98%B5/10234479 （分块矩阵，百度百科链接）

首先将B进行列分块，$B=[b_1,\dots ,b_n],b_i\in {\mathbb{R}}^d$

然后

看到这里，就可以来进行PCA算法的证明了。

PCA算法是一个降维算法，方法是使用一个线性变换将原来的高维空间的向量映射到一个低维空间。目标是找到这样一个线性变换，即一个矩阵。要求是不仅能够将原始向量从高维空间映射到低维空间，还要能够从低维空间映射回来，所以这就又需要一个变换，即又一个矩阵，并且要求映射回来的向量与原始向量尽可能的逼近。

设$x_1,\dots ,x_m$为${\mathbb{R}}^d$中的$m$个向量, 我们要将其映射到${\mathbb{R}}^n$中（n<d). 我们需要一个矩阵$W\in {\mathbb{R}}^{n,d}$将其映射过去：
$$\mathbf{x}\mapsto W\mathbf{x}$$
然后还需要一个矩阵$U\in {\mathbb{R}}^{d,n}$，可以用来恢复每一个向量的压缩版本，即对于一个压缩后的向量$\mathbf{y}=W\mathbf{x}$， 我们可以构造$\tilde{\mathbf{x}}=U\mathbf{y}$，使得$\tilde{\mathbf{x}}=U\mathbf{y}$位于原始高维空间${\mathbb{R}}^d$, 且尽可能与原始向量之间的平方距离尽可能小，就是下面这样一个优化问题：
$$\underset{W\in {\mathbb{R}}^{n,d},U\in {\mathbb{R}}^{d,n}}{\mathrm{argmin}}\sum _{i=1}^m{\Vert {\mathbf{x}}_i-UW{\mathbf{x}}_i\Vert }_2^2$$
首先，我们证明解集一定满足下面这种形式：

$U$的列向量组是标准正交的，且$W$是$U$的转置矩阵。

证明可参见矩阵分析引理23.1，由于时间关系，先放一放。

上述结论说明，解集是引理23.1中满足条件的U,W组成的集合的子集。

于是，上述优化问题可以将搜索范围进一步缩小：
$$\underset{U\in {\mathbb{R}}^{d,n}:U^{\top }U=I}{\mathrm{argmin}}\sum _{i=1}{\Vert {\mathbf{x}}_i-U{U}^{\top }{\mathbf{x}}_i\Vert }_2^2.$$
上述目标函数可以化为：

由于矩阵的迹是一个线性算子，所以累加符号可以与迹运算进行交换，进一步将上述问题转化为：
$$\underset{U\in {\mathbb{R}}^{d,n}:U^{\top }U=I}{\mathrm{argmax}}\mathrm{trace}\left(U^{\top }\sum _{i=1}^m{\mathbf{x}}_i{\mathbf{x}}_i^{\top }U\right)$$
令$A={\sum }_{i=1}^m{\mathbf{x}}_i{\mathbf{x}}_i^{\top }$， 那么问题则转化为：
$$\underset{U\in {\mathbb{R}}^{d,n}:U^{\top }U=I}{\mathrm{argmax}}\mathrm{trace}\left(U^{\top }AU\right)$$
如何求解该优化问题？首先要能够对目标函数进行计算：

可以验证矩阵A是对称矩阵，而对称矩阵是正规矩阵，正规矩阵又可以进行谱分解，写出其谱分解形式$A=VD{V}^T$， 其中$D$为对角阵，对角元素为$A$的特征值，$V$为酉矩阵，即$V{V}^T=V^{T}V=I$, 且$V$的列向量组为$A$的特征向量。

则
$$\mathrm{trace}\left(U^{\top }AU\right)=\mathrm{trace}\left(U^{\top }VD{V}^{T}U\right)$$

进行一个变量代换，令$B=V^{T}U\in {\mathbb{R}}^{d,n}$

于是，便有了下面的推导：

注：经过一下演算（通过半正定二次型的定义），可知$A$是半正定矩阵，所以矩阵D的对角元素均非负。

主要思路是通过Von Neumann提出的埃尔米特半正定复方阵乘积的迹不等式。

8 幂等矩阵(idempotent matrix)

若一个矩阵是方阵，且矩阵的平方仍为自己，则称该方阵为幂等矩阵。（顾名思义，取幂仍为自己的矩阵称为幂等矩阵）

性质：

• 幂等矩阵的迹等于幂等矩阵的秩。
• 幂等矩阵要么相似于对角元全为1或者0的对角阵。（即对角阵的对角元的元素只能是0,1，不会出现其他值）。

9 Von Neumann’s 迹不等式 wiki链接

对于两个埃尔米特的n阶半正定复方阵A, 和B, 它们的特针织现在按照递减的顺序进行排列分别为$a_1\ge a_2\ge \cdots \ge a_n$何$b_1\ge \cdots \ge b_n$,

则有$\mathrm{Tr}(AB)\le {\sum }_{i=1}^n{a}_i{b}_i$

10 矩阵相似

如果两个矩阵相似，则这两个矩阵有相同的特征值。

11 矩阵的特征值与特征向量

对于一个n阶矩阵A来说，如果一个标量$\lambda$和一个非零向量$x$满足
$$Ax=\lambda x,x\in C^n,x\ne 0,\lambda \in C$$
则$\lambda$称为A的一个特征值， $x$称为A属于$\lambda$的特征向量。$(\lambda ,x)$是矩阵$A$的一个特征对。

特征值和特征向量从来都是成对出现的。

12 正规矩阵

正规矩阵是非常重要的一类矩阵：它包括

酉矩阵、埃尔米特矩阵、斜埃尔米特矩阵(skew Hermitian)、实正交矩阵、实对称矩阵、实斜对称矩阵。

正规矩阵的定义： 如果一个n维矩阵A满足它和它的共轭转置矩阵是可交换的，则称该矩阵是正规矩阵。

正规矩阵的性质：

13 正定矩阵、半正定矩阵

有一类埃尔米特矩阵，它们有一个特殊的正的性质，它们自然地出现在很多应用中。带有这种正性的埃尔米特矩阵也将正数推广到了矩阵上。这个观察经常为正定矩阵的应用和性质提供了新的视角。下面一些例子也展现了这种特殊的埃尔米特矩阵的出现的方式。

例如 Hessian矩阵、协方差矩阵等。

正定矩阵

定义:称一个埃尔米特矩阵是正定的，如果对于任意的复数域上的非零向量，其二次型均为正数，则称该矩阵是正定矩阵。

同理，如果二次型为非负数，则称该矩阵为半正定矩阵。

参考文献

[1] https://math.stackexchange.com/questions/1902421/prove-that-the-trace-of-the-matrix-product-uau-is-maximized-by-setting-us