Principle Component Analysis 主成分分析

---

Intro

PCA is one of the most important and widely used dimension reduction algorithm. Other dimension reduction algorithm include LDA, LLE and Laplacian Eigenmaps.
You can regard PCA as a one layer neural network with nD input and mD output.
PCA reject nD data to mD with the maximum various.

PCA

We want to reduct data from nD to mD.
$Y = AX$Y=AX
$Y - R^{m*1} \\ A- R^{m*n} \\ X-R^{n*1}$Y−Rm∗1A−Rm∗nX−Rn∗1

$A = \begin{bmatrix} -a_1-\\ -a_2- \\ ... \\ -a_m- \end{bmatrix} Y = \begin{bmatrix} a_1(x-\bar{x})\\ a_2(x-\bar{x}) \\ ... \\ a_m(x-\bar{x}) \end{bmatrix}$A=⎣⎢⎢⎡​−a1​−−a2​−...−am​−​⎦⎥⎥⎤​Y=⎣⎢⎢⎡​a1​(x−xˉ)a2​(x−xˉ)...am​(x−xˉ)​⎦⎥⎥⎤​

$\left\{\begin{array}{l} Y = A(X - \bar{X}) \\ \bar x = E(X) = \frac1p\sum\limits_{p=1}^Px_p \end{array}\right.$⎩⎨⎧​Y=A(X−Xˉ)xˉ=E(X)=p1​p=1∑P​xp​​

$\max \sum\limits_{i=1}^P(y_i - \bar y_i)^2$maxi=1∑P​(yi​−yˉ​i​)2
$\bar y_i = \frac1p\sum\limits_{i=1}^Py_i = \frac {a_i}{p}(\sum\limits_{i=1}^Px_i - p\bar x) = 0$yˉ​i​=p1​i=1∑P​yi​=pai​​(i=1∑P​xi​−pxˉ)=0
$\sum\limits_{i=1}^P(y_i - \bar y_i)^2 = \sum\limits_{i=1}^P[a_1(x_i - \bar x)]^2 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum\limits_{i=1}^Pa_1[(x_i-\bar x)(x_i - \bar x)^T]a_1^T \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =a_1\sum\limits_{i=1}^P[(x_i-\bar x)(x_i - \bar x)^T]a_1^T \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =a_1\Sigma a_1^T$i=1∑P​(yi​−yˉ​i​)2=i=1∑P​[a1​(xi​−xˉ)]2                      =i=1∑P​a1​[(xi​−xˉ)(xi​−xˉ)T]a1T​                      =a1​i=1∑P​[(xi​−xˉ)(xi​−xˉ)T]a1T​                      =a1​Σa1T​
$\Sigma$Σ – covariance matrix

Our target:
$\left\{\begin{array}{l} \max \ \ a_1\Sigma a_1^T\\ s.t. \ \ \ \ \ a_1a_1^T = ||a_1||^2 = 1 \end{array}\right.${max  a1​Σa1T​s.t.     a1​a1T​=∣∣a1​∣∣2=1​
apply Lagrange multiplier method:
$E(a_1) = a_1\Sigma a_1^T - \lambda_1(a_1a_1^T -1) \\ \frac{\partial E}{\partial a_1} = (\Sigma a_1^T - \lambda_1a_1^T)^T = 0 \\ \Sigma a_1^T = \lambda_1a_1^T$E(a1​)=a1​Σa1T​−λ1​(a1​a1T​−1)∂a1​∂E​=(Σa1T​−λ1​a1T​)T=0Σa1T​=λ1​a1T​
$\lambda_1$λ1​ is the largest eigenvalue of $\Sigma$Σ, and $a_1$a1​ is its eigenvector.

$\left\{\begin{array}{l} \max \ \ a_2\Sigma a_2^T\\ s.t. \ \ \ \ \ a_2a_2^T = ||a_2||^2 = 1 \end{array}\right.${max  a2​Σa2T​s.t.     a2​a2T​=∣∣a2​∣∣2=1​
…(same method)
$\lambda_2$λ2​ is the second largest eigenvalue of $\Sigma$Σ, and $a_2$a2​ is its eigenvector.

…

Summary

① find the value of $\Sigma$Σ
② find the eigenvalues $a_i$ai​ of $\Sigma$Σ and sort them
③ normalize $a_i$ai​, let $a_1a_1^T=1$a1​a1T​=1
④ $A = \begin{bmatrix} -a_1-\\ -a_2- \\ ... \\ -a_m- \end{bmatrix} Y = \begin{bmatrix} a_1(x-\bar{x})\\ a_2(x-\bar{x}) \\ ... \\ a_m(x-\bar{x}) \end{bmatrix}$A=⎣⎢⎢⎡​−a1​−−a2​−...−am​−​⎦⎥⎥⎤​Y=⎣⎢⎢⎡​a1​(x−xˉ)a2​(x−xˉ)...am​(x−xˉ)​⎦⎥⎥⎤​

⑤ $Y = A(X - \bar{X})$Y=A(X−Xˉ)