（八）从优化的角度解释PCA

Let A be a given $n\times p$ matrix and $\phi$ be $\phi(\vec{v},\vec{z})=\frac{1}{2}tr((A-Z\cdot\ V^{T})(A-Z\cdot\ V^{T})^{T})=||A-Z\cdot\ V^{T}||^{2}_{F}$ where $V\in R^{p\times q}$ satisfies $V^{T}V=I_{q}$ and $Z \in R^{n\times q}$ ;The Minimum of $\phi$ is obtained when $V$ is an $p \times q$ matrix of orthogonal eigenvalues associated to the q largest eigenvalues of $A^{T}A$ and $Z=AV$ .

我们试图从优化的角度切入PCA：
优化问题有3要素：
1.目标函数: $\phi$
2.决策变量: $V,Z;$
3.约束条件: $V^{T}V=I_{q};$
$opt. min\space tr((A-Z\cdot V^{T})(A-Z\cdot V^{T})^{T}) \\s.t.\space \space \space \space V^{T}V=I_{q};$
这就涉及一些问题，我们的目的是什么，这点很明显可以从目标函数中看出。先看个特殊情况，如果Z已知，我们将Z投影到正交向量构成的空间中，我们的目的是让数据矩阵A与正交变换后的Z对齐。
细致看下这个特殊情况:
$tr((A-Z\cdot V^{T})(A-Z\cdot V^{T})^{T})\\ =tr(A^{T}A)+tr(Z\cdot V^{T}\cdot (Z\cdot V^{T})^{T})-2\cdot tr(AZV^{T})\\ =tr(A^{T}A)+tr(Z\cdot V^{T}\cdot V \cdot Z^{T} )-2\cdot tr(AZV^{T})\\ =tr(A^{T}A)+tr(Z\cdot Z^{T} )-2\cdot tr(AVZ^{T})$
因为在上述结果的最后，前两项是已知常数；所以我们实际上是要最大化 $tr(AVZ^{T})=tr(Z^{T}AV)$ 我们可以对 $Z^{T}A$ 做奇异值分解。即：
$Z^{T}A=Q\Lambda R^{T}$
令 $R^{T}VQ=B$ ;R,V,Q都是正交矩阵，所以B也是正交矩阵。所以：
$tr(AZ^{T}V)=tr(Q\Lambda R^{T}V)=tr(\Lambda R^{T}VQ)=tr(\Lambda B)=\sum_{i=1}^{n}B_{ii}\lambda{i}\leq \sum_{i=1}^{n}\lambda_{i}$
最后一个不等式成立的原因是 $B$ 是个正交矩阵，因为所有正交矩阵都是经过单位化的，所以对角线元素都小于1。等号成立的条件是 $B$ 是单位矩阵且 $p=q$ 。即：
$V=RQ^{T}$ 时，我们的目标函数最小，相当于Z转一个角度能与原来矩阵对齐。而旋转变换的正交矩阵取决于 $Z^{T}A$ 奇异值分解出的两个正交的特征向量矩阵。
这说明我们只要知道了降维后的 $Z$ ，那么我们总能找到一个变换 $V$ ，使得 $Z$ 在变换后尽可能的还原 $A$ 的信息。
那么问题来了， $Z$ 就是我们所要求的东西，我们不可能提前知道，那么我们怎么求满足条件,且尽可能还原 $A$ 的信息的 $Z$ 和 $V$ 呢？现在我们得直面这个优化问题了。
我们可以靠拉格朗日乘子法将原来的有约束的优化问题转为无约束的优化问题,最后求导后找出满足条件的其中一组解就可以了。
所以
$Min\space L=\frac{1}{2}tr((A-Z\cdot\ V^{T})(A-Z\cdot\ V^{T})^{T})-\frac{1}{2}tr(C(V^{T}V-I_{q}))$
对各个决策变量求导：
$dL_{Z}=\frac{1}{2}tr(-(dZ)\cdot\ V^{T}(A-Z\cdot\ V^{T})^{T}-(A-Z\cdot\ V^{T})((dZ)\cdot\ V^{T})^{T})\\=-tr((A-Z\cdot\ V^{T})VdZ^{T}) \\\frac{dL}{dZ}=(A-Z\cdot\ V^{T})V=AV-Z\cdot\ V^{T}V------(1)\\ dL_{V}=-\frac{1}{2}tr(ZdV^{T}(A-ZV^{T})^{T}+(A-ZV^{T})dV\cdot Z^{T})-tr(C(dV^{T})V+CV^{T}(dV))\\ =-tr((VZ^{T}Z-A^{T}Z-VC)dV^{T})\\ \frac{dL}{dV}=VZ^{T}Z-A^{T}Z-VC------(2)\\ \frac{dL}{dC}=V^{T}V-I_{q}------(3)$
令(1),(2),(3)导数等于0：
$\frac{dL}{dZ}=(A-Z\cdot\ V^{T})V=AV-Z\cdot\ V^{T}V=0\\ \frac{dL}{dV}=VZ^{T}Z-A^{T}Z-VC=0\\ \frac{dL}{dC}=V^{T}V-I_{q}=0\\ 所以有：\\ Z=AV\\ C=0\\$
然而我们的目的是找出其中一个解就行，也就是找到其中一个V，所以我们将 $Z=AV;C=0$ 带入(2)中：
$VV^{T}A^{T}AV=A^{T}AV$
令 $V^{T}A^{T}AV=\Lambda;\Lambda是特征值对角矩阵$ ，那么： $A^{T}A=V^{T}\Lambda V$ 即 $V$ 可以通过对 $A^{T}A$ 特征分解后取前 $q$ 个最大的特征值得到。这是其中一个解，也是我们想要的结果，即直接可以通过数据矩阵 $A$ 的信息得出我们的正交变换 $V$ ；使得数据在保证信息尽可能完整的情况下降维。
(矩阵求导方面可以参考这里)