[toc]
Algebraic Definition of PCA Input $A\in R^{n\times d}$ , find a matrix A, where $rank(A)=k$ , s.t. $\min|A-A_k|_F$
$A=\left[\begin{array}{c}
P_1\P_2\\vdots\P_n
\end{array}\right]$, $A_k=\left[\begin{array}{c}
\pi{(P_1)}^T\
\pi{(P_2)}^T\
\vdots\
\pi{(P_n)}^T
\end{array}\right]$
即用一个点近似所有数据点的分布, $\forall i, \pi(P_i)=q$ , then target becomes
$$\min\sum\limits_{i=1}^n|P_i-q|^2$$
则最优解是 $q=\frac{1}{n}\sum\limits_{i=1}^nP_i$
证明 : 令 $\mu =\frac{1}{n}\sum\limits_{i=1}^nP_i$ ,
$$\begin{aligned}
\sum\limits_{i=1}^n|P_i-q|^2 &= \sum\limits_{i=1}^n|P_i-\mu+\mu-q|^2\
&=\sum\limits_{i=1}^n\left(|P_i-\mu|^2-2\left< P_i-\mu, \mu-q\right>+|\mu-q|^2\right)\
&=\sum\limits_{i=1}^n|P_i-\mu|^2+n|\mu-q|^2\
\end{aligned}$$
此时 $\min\sum\limits_{i=1}^n|P_i-\mu|^2+n|\mu-q|^2 \Rightarrow q=\mu$
反证法: 平移 $F$ 到一个过 $\mu$ 的新平面 $F'=F+\mu-\pi(\mu)$ . 记 $\alpha$ 为空间 F 中的任一向量在正交补空间 $F^{\perp}$ 的投影, 则有 $$\sum\limits_{i=1}^n|P_i-\pi(P_i)|^2=\sum\limits_{i=1}^n|\alpha(P_i)-\alpha(F)|^2$$
由 $k=0$ 时的讨论可知 $\alpha(F)=\sum\limits_{i=1}^n\alpha(P_i)$ ,
又由 $F'$ 过 $\mu$ 知 $\alpha(F')=\frac{1}{n}\sum\limits_{i=1}^n\alpha(P_i)$ , 于是 $F=F'$ , 从而 $\mu\in F$ .
不妨设点集的重心 $u$ 为原点, 即用一条直线 $t_1$ 去近似所有数据分布, 由勾股定理:
$$\min\sum\limits_{i=1}^n|P_i-\pi(P_i)|^2=\sum\limits_{i=1}^n|P_i|^2-\sum\limits_{i=1}^n(\left< P_i,t_i\right>)^2$$
故优化问题等价于$$\max\limits_{|t_i|=1}\sum\limits_{i=1}^n(\left< P_i,t_i\right>)^2=\max\limits_{|t_i|=1}|At_1|_F^2$$
对 $A$ 做 SVD 分解, 即 $A=USV^T$ ,
其中 $U=[u_1,\cdots,u_n]$ 和 $V=[v_1\cdots v_d]$ 都是正交矩阵, 而 $S=diag{\sigma_1,\cdots,\sigma_d}$ 为对角矩阵(补齐为矩阵的). (注意这里正交变换保证了保距同构的性质.)
进而得到 $U\cdot S=[\sigma_1u_1, \cdots, \sigma_du_d, 0,\cdots,0]$ .
考虑 $d=2$ 的情形: $U\cdot S=[\sigma_1u_1, \sigma_2u_2, 0,\cdots,0]$ , $V^Tt=[\lambda_1,\lambda_2]^T$ , 其中 $\lambda_1^2+\lambda_2^2=1$ ,
于是 $A=\lambda_1\sigma_1u_1+\lambda_2\sigma_2u_2$ , 令 $x=\lambda_1\sigma_1u_1, y = \lambda_2\sigma_2u_2$ , 则 $\left(\frac{x}{\sigma_1u_1}\right)^2+\left(\frac{y}{\sigma_2u_2}\right)^2=1$
为了 $\max\limits_{|t_i|=1}\sum\limits_{i=1}^n(\left< P_i,t_i\right>)^2=\max\limits_{|t_i|=1}|At_1|F^2=\max\limits {|t_1|=1}(\lambda_1\sigma_1u_1)^2+(\lambda_2\sigma_2u_2)^2=\max\limits_{|t_1|=1}x^2+y^2$, 可得 $x=\pm\sigma_1u_1, y=0\Rightarrow V^Tt_1=(\pm1,0)\Rightarrow t_1=\pm v_1$
同理可得, 当 $d\ge2$ 时, $t_1=\pm v_1$
可以猜测: $F=span{v_1,v_2,\cdots,v_k}$
反证: 假设 $v_1\notin F$ , 设 $F=span{t_1,\cdots,t_k}$
令 $t_1=\frac{\pi(v_1)}{|\pi(v_1)|}$ , 于是可构造 $F'=span{v_1,\cdots,t_k}$ ,
类比 $k=1$ 情形, 有
$\sum\limits_{i=1}^n|P_i-\pi(P_i)|^2=\sum\limits_{i=1}^n|P_i|^2-\sum\limits_{i=1}^n\left(|\left< P_i,t_1\right>|^2+\cdots+|\left< P_i,t_k\right>|^2\right)$
于是, 优化问题等价于 $\max\sum\limits_{i=1}^n\left(|\left< P_i,t_1\right>|^2+\cdots+|\left< P_i,t_k\right>|^2\right)$ ,记该目标函数为 $\alpha_F$ .
而在 F' 上相应有 $\alpha_{F'}=\sum\limits_{i=1}^n\left(|\left< P_i,v_1\right>|^2+\cdots
+|\left< P_i,t_k\right>|^2\right)$
由 $k=1$ 的情况知 $\sum\limits_{i=1}^n|\left< P_i,v_1\right>|^2 > \sum\limits_{i=1}^n|\left< P_i,t_1\right>|^2$
因此 $\alpha_{F'}\ge\alpha_F$ , 即 $F'$ 是最优超平面 $\Rightarrow v_1$ 在最优 $k$ 维超平面上.
以此类推即得 ${v_1,\cdots,v_k}\subset $ 最优的 $k$ 维超平面上, 又由于 $v_i$ 相互正交, 构成 F 的一个基, 故最优超平面 F 在由 $v_i$ 张成的一个椭球上.
SVD 复杂度高
近似计算特征向量, 有数值精度问题
对于大规模数据由于需要多次读取不适合分布式和流数据问题(?)