forked from ArquintL/eth-cil-exam-summary
-
Notifications
You must be signed in to change notification settings - Fork 1
/
PCA.tex
35 lines (33 loc) · 3.12 KB
/
PCA.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
\section*{Principal Component Analysis}
$\mathbf{X} \in \mathbb{R}^{D \times N}$. $N$ observations, $K$ rank.\\
1. Empirical Mean: $\overline{\mathbf{x}} = \frac{1}{N} \sum_{n=1}^N \mathbf{x}_n$.\\
2. Center Data: $\overline{\mathbf{X}} = \mathbf{X} - [\overline{\mathbf{x}}, \ldots, \overline{\mathbf{x}}] = \mathbf{X} - \mathbf{M}$.\\
3. Cov.: $\boldsymbol{\Sigma} = \frac{1}{N } \sum_{n=1}^N (\mathbf{x}_n - \overline{\mathbf{x}}) (\mathbf{x}_n - \overline{\mathbf{x}})^\top = \frac{1}{N} \overline{\mathbf{X}}\overline{\mathbf{X}}^\top$.\\
4. Eigenvalue Decomposition: $\boldsymbol{\Sigma} = \mathbf{U} \boldsymbol{\Lambda} \mathbf{U}^\top$.\\
5. Select $K < D$, only keep $\mathbf{U}_K, \boldsymbol{\lambda}_K$.\\
6. Transform data onto new Basis: $\overline{\mathbf{Z}}_K = \mathbf{U}_K^\top \overline{\mathbf{X}}$.\\
7. Reconstruct to original Basis: $\tilde{\overline{\mathbf{X}}} = \mathbf{U}_k \overline{\mathbf{Z}}_K$.\\
8. Reverse centering: $\tilde{\mathbf{X}} = \tilde{\overline{\mathbf{X}}} + \mathbf{M}$.\\
For compression save $\mathbf{U}_k, \overline{\mathbf{Z}}_K, \overline{\mathbf{x}}$.\\
$\mathbf{U}_k \in \mathbb{R}^{D \times K}, \boldsymbol{\Sigma} \in \mathbb{R}^{D \times D}, \overline{\mathbf{Z}}_K \in \mathbb{R}^{K \times N}, \overline{\mathbf{X}} \in \mathbb{R}^{D \times N}$
\subsection*{Reconstruction Error Exercise}
$\tilde {\mathbf{X}} = \mathbf{U}_K \mathbf{U}_K^\top \bar {\mathbf{X}}$, the error is $\frac{1}{N} \sum_{i=1}^N ||\tilde x_i - \bar x_i||_2^2$ \\
$=\frac{1}{N}||\tilde{\mathbf{X}}-\bar{\mathbf{X}}||_F^2 = \frac{1}{N}||(\mathbf{U}_K \mathbf{U}_K^\top - \mathbf{I}_d)\bar{\mathbf{X}}||_F^2$ \\
$= \frac{1}{N} \text{trace}((\mathbf{U}_K \mathbf{U}_K^\top - \mathbf{I}_d)\bar{\mathbf{X}} \bar{\mathbf{X}}^\top (\mathbf{U}_K \mathbf{U}_K^\top - \mathbf{I}_d)^\top)$ \\
$=\text{trace}((\mathbf{U}_K \mathbf{U}_K^\top - \mathbf{I}_d) \Sigma (\mathbf{U}_K \mathbf{U}_K^\top - \mathbf{I}_d))$ \ $\textcolor{gray}{\Sigma = \mathbf{U}\Lambda \mathbf{U}^\top}$ \\
$=\text{trace}((\mathbf{U}_K \mathbf{U}_K^\top \mathbf{U} - \mathbf{U})\Lambda ( \mathbf{U}^\top \mathbf{U}_K \mathbf{U}_K^\top - \mathbf{U}^\top))$ \\
$=\text{trace}(([\mathbf{U}_K ;\mathbf{0}] - \mathbf{U})\Lambda ([\mathbf{U}_K; \mathbf{0}] - \mathbf{U}^\top)) $ \\
$=\text{trace}(\sum_{i=K+1}^D \lambda_i u_i u_i^\top) = \sum_{i=K+1}^D \lambda_i \cdot \text{trace}(u_i u_i^\top)
$ \\
$=\sum_{i=K+1}^D \lambda_i$ since $\text{trace}(u_i u_i^\top) = ||u_i||_2^2 = 1$
\subsection*{Iterative View}
Residual $r_i$: $x_i - \tilde{x}_i = I - uu^T x_i$\\
Cov of $r$: $\frac{1}{n} \sum_{i=1}^n (I-uu^T)x_i x_i^T (I-uu^T)^T =$ \\
$(I-uu^T) \Sigma (I-uu^T)^T = \Sigma - 2\Sigma u u^T + u u^T \Sigma u u ^T = \Sigma - \lambda uu^T$ \\
1. Find principal eigenvector of $(\Sigma - \lambda u u^T)$\\
2. Which is the second eigenvector of $\Sigma$\\
3. Iterating to get $d$ principal eigenvector of $\Sigma$
\subsection*{Power Method}
Power iteration: $v_{t+1} = \frac{Av_t}{||Av_t||}$, $\lim_{t \rightarrow \infty} v_t = u_1$\\
Assuming $\langle u_1, v_0 \rangle \not = 0$ and $|\lambda_1| > |\lambda_j| (\forall j \geq 2)$
Then $\lambda_1 = \lim_{t\to \infty}||\mathbf{Av}_t||/||\mathbf{v}_t||$