The Principal Component Analysis (PCA) tries to find out the directions along which the projected data has maximum variance, which are the same directions along which the minimum reconstruction error occurs.
In order to perform PCA on a dataset \(\mathcal{D} = \{ x_1, x_2, \ldots, x_n\}\) where each of the datapoint is a \(d\)-dimensional vector, the following steps can be done:
Find the mean vector \(\bar{x}\) of the dataset: \[\bar{x} = \dfrac{x_1 + x_2 + \ldots + x_n }{n}\]
Form the data matrix: \[X = \begin{bmatrix} \vert & \vert & & \vert \\ x_1-\bar{x} & x_2 - \bar{x} & \ldots & x_n -\bar{x} \\ \vert & \vert & & \vert \end{bmatrix}\]
Obtain the covariance matrix: \[C = \dfrac{1}{n} XX^T = \dfrac{1}{n} \sum_{i=1}^n (x_i-\bar{x}) (x_i-\bar{x})^T\]
Find the eigenvalues of \(C\) and arrange them in the descending order: \[\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_d\] and the associated unit eigenvectors \(u_1\), \(u_2\), \(\ldots\), \(u_d\).
The eigenvector \(u_1\) associated with the greatest eigenvalue \(\lambda_1\) is referred to as the first principal component, the vector \(u_2\) associated with the eigenvalue \(\lambda_2\) is called the second principal component and so on.
The principal components are orthogonal to each other.
The projection \(z_i\) of the datapoint \(x_i\), onto an \(m\)-dimensional subspace, where \(m<d\), is obtained as follows: \[z_i = \sum_{j=1}^m (x_i^Tu_j)u_j + \sum_{j=m+1}^d (\bar{x}^Tu_j)u_j\] for each \(i=1, 2, \ldots n\).
The projection \(z_i\) of the datapoint \(x_i\), onto the first principal component \(u_1\), is obtained as follows: \[z_i = (x_i^Tu_1)u_1 + \sum_{j=2}^d (\bar{x}^Tu_j)u_j\]
The reconstruction error is \[J = \dfrac{1}{n}\sum_{i=1}^n \Vert x_i -z_i \Vert^2\]
The variance of the projected data along the \(i\)-th principal component is equal to the corresponding eigenvalue \(\lambda_i\).
If the dataset is very high dimensional, so that \(d \gg n\), PCA can still be efficiently implementing by considering \[C = \dfrac{1}{n} X^TX\] which is of size \(n\times n\), instead of the \(d\times d\) matrix \(C=\dfrac{1}{n}XX^T\).