Data Science Part 25: Principal Component Analysis

In Principal component analysis, we have a point cloud of data and can apply a transformation. We want a transformation that arranges most of the variance in a point cloud spanning a few dimensions. We might be able to throw away a few dimensions with little information to make things more efficient. 

We will soon compute this transform. An application of PCA is identifying digits. We can apply PCA to each digit and identify the M principal components u1, u2, ..., uM and we will subsequently multiply the data by the principal components. The digit probably appeared for large numbers, else it's nothing. 

In contrast with the sparsifying transform, where we know where the signal is sparse and we don't know where the big coefficients are, in PCA, we statistically know where the big coefficients are.  

The derivation of PCA is as follows:

The point cloud is comprised of N vectors, 𝑥𝑛 ∈ ℝD. We begin with the best projection vector u1 ∈ ℝD. It packs as much average energy as possible. The expectation is E[u1Tx] = u1TE[x]. The variance var(u1Tx) = E[(u1Tx - E[u1Tx])^2]. We can show var(u1Tx) = u1TSu1.  The following is the covariance matrix of the data, which by definition, is a square matrix giving the covariance between each pair of elements of a given random vector.

We want to solve u1 by maximizing the equation 

with the Lagrangian λ. We can show that the solution satisfies Su1 = λ1u1 which implies that ( λ1, u1) are eigen value/vector pairs to s. The variance satisfies the condition u1TSu1 = u1Tλ1u1 = λ1. The optimal M-dimensional projection corresponds to the M eigenvectors corresponding to the largest eigenvalues. 

However, the issue can be that we may not be able to compute principal components. The solution to this is to compute M < D random projections of data. The solution is to compute M < D random projections of data. On average, especially in high dimensions, random projections are approximately energy preserving, as it preserves the geometric structure of space. Surprisingly, the random projections are not that far from optimal. 

We consider a point cloud of N vectors in a D dimensional space and we want to find a transformation UTX that packs the most energy in a few energy coefficients. 

Instead of computing energy from scratch, we want to have vector u1 to pack as much energy as possible when applied to X.

We can then generate a covariance matrix of X as follows: 

From the U equation denoted inside the transformation equation, we want to maximize U1TSu1 and maximize in turn Su1 =  λ1u1 which means that to optimize u1, we want to select  λ1 to be the largest eigen value of S. 

We can compute the next vector u2, by selecting the second largest eigenvalue  λ2. The M principle components correspond into the M eigenvectors of S whose respective eigen values are the largest, with the variance just been the sum of the  λ's. It is a form of dimensionality reduction while capturing most features of the data. 

Covariance matrix will rely on actual numbers while correlation matrix will rely on percentiles. PC1 will be the largest eigenvector, PC2 will be the second larges, and on and on and on. We also prioritize whatever part of the matrices have the most amount of variation. Larger eigenvalues will result in more variation of the dataset explained and the more eigenvalues included, the more variations of the dataset successfully explained. If there are only a few dimensions/variables that make up around 99% of the data, then it would make sense to discard the rest of the data just to simplify things. We can plot PC1 against PC2 and will show a reasonable variation already between the data points: