principal component analysis

problem statement

map $x \in R^d$ to $z \in \mathbb{R}^q$ with $q < d$
A $q \times d$ $q \times d$ matrix can represent a linear mapping: $z = Ax$
- Assume that $A A^T = I$ (orthonormal matrix)

Given $X \in \mathbb{R}^{d \times n}$ , find $A$ that minimises the reconstruction error: $\min\limits_{A,B} \sum_{i} \| x^i - B A x^i \|_2^2$

if $q=d$ , then error is zero.

Solution:

$B = A^T$
$\min\limits_{A} \sum_i \| x^i - A^T A x^i \|^2$ is subjected to $A A^T = I_{q \times q}$
assuming data is centered, or $\frac{1}{n} \sum\_{i} x^i = \begin{bmatrix} 0 & \cdots & 0 \end{bmatrix}^T$

\begin{aligned} X^T X \mathcal{u} &= \lambda \mathcal{u} \\ X^T X &= U^T \Lambda U \\ \\ \\ \because \Lambda &= \text{diag}(\lambda_1, \lambda_2, \cdots, \lambda_d) \\ &= \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_q \end{bmatrix} \end{aligned}

Idea: given input $x^1, \cdots, x^n \in \mathbb{R}^d$ , $\mu = \frac{1}{n} \sum_{i} x^i$

Thus

C = \sum (x^i - \mu)(x^i - \mu)^T

Find the eigenvectors/values of $C$ :

C = U^T \Lambda U

Optimal $A$ is:

A = \begin{bmatrix} u_1^T \\ u_2^T \\ \vdots \\ u_q^T \end{bmatrix}