Principal Component Analysis

Assume that we have $n$ $d$-dimensional data vectors ${\bf x}_1,{\bf x}_2,\ldots,{\bf x}_n$, which form the $d\times n$ data matrix $\mathbf{X}$ = $[{\bf x}_1,{\bf x}_2,\ldots,{\bf x}_n]$. The matrix $\mathbf{X}$ is decomposed into $\mathbf{X}\approx \mathbf{A}\mathbf{S}$, where $\mathbf{A}$ is a $d\times c$ matrix, $\mathbf{S}$ is a $c\times n$ matrix and $c\leq d \leq n$. Principal subspace methods [6,4] find such $\mathbf{A}$ and $\mathbf{S}$ that the reconstruction error

$$C = \lVert \mathbf{X}- \mathbf{A}\mathbf{S}\rVert _F^2 = \sum_{i=1}^d \sum_{j=1}^n ( x_{ij} - \sum_{k=1}^c a_{ik} s_{kj} )^2\, ,$$ (1)

is minimized. Typically the row-wise mean is removed from $\mathbf{X}$ as a preprocessing step. Without any further constraints, there exist infinitely many ways to perform such a decomposition. PCA constraints the solution by further requiring that the column vectors of $\mathbf{A}$ are of unit norm and mutually orthogonal and the row vectors of $\mathbf{S}$ are also mutually orthogonal [3,4,2,5].

There are many ways to solve PCA [6,4,2]. We will concentrate on the subspace learning algorithm that can be easily adapted for the case of missing values and further extended.