4.2. Principal Component Analysis

Principal Component Analysis (PCA)

For a data matrix $A=\left[\begin{array}{ccc}{\vec{x}}_1& \dots & {\vec{x}}_n\end{array}\right]\in {\mathbb{R}}^{d\times n}$ with SVD $A=U\Sigma V^T$,

1. $U_l\in {\sum }_{i=1}^n\underset{W\in {\mathbb{R}}^{d\times l}}{\mathrm{argmin}}||{\vec{x}}_i-W^{T}W{\vec{x}}_i|{|}^2,$
   where $W\in {\mathbb{R}}^{d\times l}$ is an orthonormal matrix such that $W^{T}W=I_l$, and $U_l$ consists of the first $l$ columns of the matrix of principal components $U$.

2. $S_{\text{PCA}}\in {\sum }_{i=1}^n\underset{S\subseteq {\mathbb{R}}^d}{\mathrm{argmin}}||{\vec{x}}_i-{\mathrm{proj}}_S({\vec{x}}_i){\vec{x}}_i|{|}^2,$
   where $\dim (S)\le l$, and $S_{\text{PCA}}=\mathrm{Span}({\vec{u}}_1,\dots ,{\vec{u}}_l)$ is the span of the first $l$ columns of the matrix of principal components $U$.

Intuition

We can compute the PCA of a data matrix $A\in {\mathbb{R}}^{d\times n}$ by first centering $A$ around the mean of its datapoints ($\frac{1}{n}A{\vec{1}}_n$) s.t. $D=A(I_n-\frac{1}{n}{\vec{1}}_n{\vec{1}}_n^T)$. Then, $\mathrm{rank}(D)=r\le \min \{m,n\}$. Suppose that the ground truth data matrix (containing the noiseless data) in reality spans an $l$-dimensional subspace $S_{gt}\subseteq {\mathbb{R}}^d$, such that $l\le r$. Then, the remaining $r-l$ dimensions of $D$ are due to noise. The goal of PCA is to extract the “best” $l$-dimensional subspace from the noisy data such that it minimizes the distance between the real subspace and our approximation. We can see the differences between this optimization approach and least squares optimization below:

We can s