主成分分析 Principal Component Analysis (PCA) 推導、證明 (without Lagrange multiplier)

序言：將 n 個 m 維 data $X=[x_1, x_2, ..., x_n]$ (shape of X = (m,n))
投影到某 k 維空間中，

令 $S={1 \over n} \sum^n_{i=1} (x_i - \bar{X}) ( x_i - \bar{X})^T$ ，S 之 eigenvalue ${\lambda_1}' \geq {\lambda_2}' \geq \dots$ 符合 $S u_i = {\lambda_i}' u_i$，令$[u_1, u_2,...,u_m] = U$

則如果該 k 維空間為 $span\{u_1, u_2, ..., u_k\}$ ，則投影後的 data 有最大的變異數

1. 首先證明：假設投影到相同的空間中，投影後的 data 變異數就會相同(其實蠻直觀的)

↑雖然投影在不同座標軸，但只要是投影在同空間，投影後的 data 變異數就會相同

完整一點的敘述如下：
假設投影 data 到 k 個向量中，該 k 個向量為$A=[a_1, a_2, ..., a_k]$，($a_1, a_2, ..., a_k$ 長度皆為 1 且互相垂直)，且投影到該 k 個向量後的 data 變異數為 V
而此時有另一組向量$B=[b_1, b_2, ..., b_k]$，$b_1, b_2, ..., b_k$ 長度皆為 1 且互相垂直，且span{A}=span{B}，則投影到該 k 個向量後的 data 變異數也是 V

sol: 

for x=1, 2, ..., k， data 在$a_x$的投影，所貢獻的變異數為${a_x}^T S a_x = {a_x}^T UDU^T a_x = {\alpha_{x1}}^2 {\lambda_1}' + {\alpha_{x2}}^2 {\lambda_2}' + ... +   {\alpha_{xm}}^2 {\lambda_m}'$
上式中$\alpha_{x1},  \alpha_{x2}, ..., \alpha_{xm}$ 皆為純量，且$a_x = \alpha_{x1} u_1 + \alpha_{x2} u_2 + ... + \alpha_{xm} u_m$
投影到$a_1, a_2, ..., a_k$後 data 的整體變異數為$a_1, a_2, ..., a_k$所貢獻的變異數總和
$$V = $$ $${\alpha_{11}}^2 {\lambda_1}' + {\alpha_{12}}^2 {\lambda_2}' + ... +   {\alpha_{1m}}^2 {\lambda_m}'+$$ $${\alpha_{21}}^2 {\lambda_1}' + {\alpha_{22}}^2 {\lambda_2}' + ... +   {\alpha_{2m}}^2 {\lambda_m}'+$$ $$\vdots$$ $${\alpha_{k1}}^2 {\lambda_1}' + {\alpha_{k2}}^2 {\lambda_2}' + ... +   {\alpha_{km}}^2 {\lambda_m}'$$
同理，投影到$b_1, b_2, ..., b_k$後 data 的整體變異數為
$$V_2 = $$ $${\beta_{11}}^2 {\lambda_1}' + {\beta_{12}}^2 {\lambda_2}' + ... +   {\beta_{1m}}^2 {\lambda_m}'+$$ $${\beta_{21}}^2 {\lambda_1}' + {\beta_{22}}^2 {\lambda_2}' + ... +   {\beta_{2m}}^2 {\lambda_m}'+$$ $$\vdots$$ $${\beta_{k1}}^2 {\lambda_1}' + {\beta_{k2}}^2 {\lambda_2}' + ... +   {\beta_{km}}^2 {\lambda_m}'$$其中$b_x = \beta_{x1} u_1 + \beta_{x2} u_2 + ... + \beta_{xm} u_m \forall x=1, ..., k$

投影到 A 的部分，觀察有${\lambda_1}'$的部分，其總和為$({\alpha_{11}}^2+{\alpha_{21}}^2+...+{\alpha_{k1}}^2){\lambda_1}'$
$({\alpha_{11}}^2+{\alpha_{21}}^2+...+{\alpha_{k1}}^2)$為$u_1$投影到該空間的向量長度
$(設u_1投影到該空間的向量為x，x^T x = (\alpha_{11}a_1 + \alpha_{21}a_2 + ... + \alpha_{k1}a_k)^T(\alpha_{11}a_1 + \alpha_{21}a_2 + ... + \alpha_{k1}a_k))$
因 x 同時等於$\beta_{11}b_1 + \beta_{21}b_2 + ... + \beta_{k1}b_k$，${\alpha_{11}}^2+{\alpha_{21}}^2+...+{\alpha_{k1}}^2 = {\beta_{11}}^2+{\beta_{21}}^2+...+{\beta_{k1}}^2$
其他${\lambda_2}', {\lambda_3}', ...$的部分可以以此類推，最後可得$V_2 = V$

2. 接著證明以下敘述：

將 data 投影到某 k 維空間中，
則如果該 k 維空間為 $span\{u_1, u_2, ..., u_k\}$ ，則投影後的 data 有最大的變異數

sol:
使用反證法：假設存在 k 個長度為 1 且互相垂直的向量  $C=[c_1, c_2, ..., c_k]$，data 投影到 C 的變異數為 V' > V。

接著我們觀察 C ，對其中任一個向量 $c_x$，其可寫為：$$c_x = \gamma_{x1}{u_1}' + \gamma_{x2}{u_2}' + ... + \gamma_{xm}{u_m}'  $$。 $\gamma_{x1}, \gamma_{x2}, ..., \gamma_{xm}$ 皆為純量。
我們將 k 個向量的係數以矩陣記錄下來：
$$C'=
\begin{pmatrix}
\gamma_{1,1} & \gamma_{1,2} & \cdots & \gamma_{1,m} \\
\gamma_{2,1} & \gamma_{2,2} & \cdots & \gamma_{2,m} \\
\vdots  & \vdots  & \ddots & \vdots  \\
\gamma_{k,1} & \gamma_{k,2} & \cdots & \gamma_{k,m}
\end{pmatrix}$$

更新 C' 的算法：

0. 令 i = m, j = k

1. 對於第 i 個 column ，可以看有沒有非 0 值，有的話想辦法消掉：
假設有 $\gamma_{x,m}\neq0$，則將 row x 與 row j 交換
$C'=
\begin{pmatrix}
\gamma_{1,1} & \gamma_{1,2} & \cdots & \gamma_{1,i} & \dots \\
\gamma_{2,1} & \gamma_{2,2} & \cdots & \gamma_{2,i} & \dots \\
\vdots  & \vdots  & \ddots & \vdots  & \dots \\
\gamma_{j,1} & \gamma_{j,2} & \cdots & \gamma_{j,i} \neq 0 & \dots \\
\vdots  & \vdots  & \ddots & \vdots & \ddots \\
\end{pmatrix}$
對於其他的非 0 值，假設有 $\gamma_{x',i}\neq 0$，可以令$\kappa = -{ \gamma_{x_i,i} \over  \gamma_{j,i}}$，assign $c_{x'}$ := ${1\over \sqrt{1+\kappa^2}} (c_{x'} + \kappa c_{j})$ ，和 assign ${c_j}$ := ${1\over \sqrt{1+\kappa^2}}(-\kappa c_{x'} + c_{j})$
使得 $\gamma_{x_i,i}=0$，且每個 row 長度維持為 1、列空間維持不變 ( data 投影在 $C' U^T$之列空間 的變異數維持不變)
對於其他的非 0 值可以比照辦理，最後矩陣可改寫成：
$C'=
\begin{pmatrix}
\gamma_{1,1} & \gamma_{1,2} & \cdots & 0 & \dots \\
\gamma_{2,1} & \gamma_{2,2} & \cdots & 0 & \dots \\
\vdots  & \vdots  & \ddots & \vdots  & \dots \\
\gamma_{j-1,1} & \gamma_{j-1,2} & \cdots & 0 & \dots \\
\gamma_{j,1} & \gamma_{j,2} & \cdots & \gamma_{j,i} \neq 0 & \dots \\
\vdots  & \vdots  & \ddots & \vdots & \ddots \\
\end{pmatrix}$

2.  假設 $\gamma_{j,1},  \gamma_{j,2}, \cdots, \gamma_{j,i-1}$ 不全為 0
則可以令 $\kappa' = \sqrt{{1\over 1- {\gamma_{j,i}}^2}}$ ，assign ${c_j}$ := $[\kappa' \gamma_{j,1},  \kappa' \gamma_{j,2}, \cdots, \kappa' \gamma_{j,i-1}, 0]$
使 $c_j$ 長度維持為 1 ($({\kappa'}^2-1) {\gamma_{j,1}}^2 +  ({\kappa'}^2-1) {\gamma_{j,2}}^2 + \cdots + ({\kappa'}^2-1) {\gamma_{j,i-1}}^2 = {\gamma_{j,i}}^2$)
、每個 row 之間仍互相垂直、且新 $c_j U^T$ 所貢獻的變異數 $\geq$ 原本 $c_j U^T$ 所貢獻的變異數
$(({\kappa'}^2-1) {\gamma_{j,1}}^2 {\lambda_1}' +  ({\kappa'}^2-1) {\gamma_{j,2}}^2 {\lambda_2}' + \cdots + ({\kappa'}^2-1) {\gamma_{j,i-1}}^2 {\lambda_{i-1}}'\geq
$
$({\kappa'}^2-1) {\gamma_{j,1}}^2 {\lambda_i}' +  ({\kappa'}^2-1) {\gamma_{j,2}}^2 {\lambda_i}' + \cdots + ({\kappa'}^2-1) {\gamma_{j,i-1}}^2 {\lambda_{i}}' = {\gamma_{j,i}}^2 {\lambda_i}')$

也有可能 $\gamma_{j,1},  \gamma_{j,2}, \cdots, \gamma_{j,i-1}$ 全為 0，如此$\gamma_{j,i}$ 則為 1。

3. 如果 column i 不全為 0 ，更新 ( i, j ) := ( i-1, j )，否則更新 ( i, j ) := ( i-1, j-1)
更新完後回到步驟 1.

做完算法後的矩陣會變為：
$$ C'=
\begin{pmatrix}
X & X & \cdots & & X_{index={c_1}} & 0 & 0  & \cdots &\cdots&\cdots& \cdots& 0 \\
0 & 0 & \cdots & \cdots & 0 & 1_{index={c_2>c_1}} & 0 &0 & \cdots & \cdots&\cdots& 0 \\
0 & 0 & \cdots & \cdots & \cdots & 0& 1_{index={c_3>c_2}} & 0 &0 & \cdots &\cdots & 0 \\
\vdots  & \vdots  & \ddots & \vdots  & \vdots  & \vdots  & \vdots & \vdots & \vdots & \vdots & \vdots   & \vdots\\
0 & 0 & \cdots & \cdots & \cdots & \cdots & 0 & 1_{index={c_k>c_{k-1}}} & 0 &0 & \cdots & 0 \\
\end{pmatrix}$$

=> Data 投影在 $C' U^T$之列空間 的變異數 $\geq V' > V$
但其 $\leq$ data 投影在 $\begin{pmatrix}I|0\end{pmatrix} U^T$之列空間 的變異數。
而$\begin{pmatrix}I|0\end{pmatrix} U^T$ 則為 $[u_1, u_2, ..., u_k]^T$
矛盾

故得證。