Abstract

In this post, we introduce the math foundation behind principal component analysis, a simple technique for dimensionality reduction.

Reference

yang’s post (written in Chinese)

Diagonalizable matrix

The efficiency of features

The high-level idea of principal component analysis is to reduce the dimensionality of a given dataset by transforming it into a new dataset in which all variables (features) are independent of each other. We denote this transformation as follow:

where $X \in R^{m \times n}$ is the original dataset with $m$ instances and $n$ variables, $P \in R^{n \times r}$ is the reduction matrix, and $Y \in R^{m \times r}$ is the transformed dataset with $r$ variables. To better understand how information was stored in our dataset matrix $X$, we can use the concept of variance and covariance of feature variables in dataset matrix $X$. Let’s denote $v_a$ as a variable in the variable vector $v\in R^n$. The variance of $v_a$ is:

The magnitude of the variance can be used to indicate the volume of information embedded in this variable. A variable contains no information is a constant with zero variance. Covariance, as another measure, indicate the level of dependency between two variables:

To represent both variance and covariance in a matrix form, we can use the concept of covariance matrix. Let’s denote the covariance matrix of the random variables vector $v$ as $C$:

Where the diagonal of $C$ are variance of each variable, and the non-diagonal elements are covariances of any two variables. Noted that if we normalized $X$ by making all $E[v_i] = 0$, our transformed $X$ still contains the same information; therefore, our covariance matrix can be simplified as follow:

The objective of principal component analysis

From (3), we know that $C$ is the covariance matrix associated with the original dataset $X$. For the transformed dataset $Y = XP$, we can also obtain a covariance matrix $D \in R^{r \times r}$ using the same procedural as (4). Interestingly, $D$ has can be rewritten with only $P$ and $C$:

Since $D$ is a covariance matrix that contains variances and covariances of the new feature variables vector, our objective is to find a $P$ such that any two random variables of this new feature variables vector have zero covariance. In addition, because $D$ has a smaller dimension than $C$, we also want this new feature variables vector to retain as much information as possible from the original dataset. Given $r$ real values such that $\lambda_1 \geq \lambda_2 \dots \lambda_r$, we want D to be a diagonal covariance matrix:

This process of finding $P$ that turns D into a diagonal matrix is called diagonalization in linear algebra (see Diagonalizable matrix). It involves eigendecomposition of matrix $C$, which happens to be a real symmetric matrix in this case. So if we apply eigendecomposition on $C$, we get:

where $P$ is an orthogonal matrix.

Relationship with SVD

It’s also common to solve PCA problem with singular value decomposition. First, let’s apply SVD on $X$:

For $X^T X$, we have:

Given (7) and (9), it’s not difficult to see that $P = V$ and $m D = \Sigma^2$, where $m$ is a constant. This means we can solve PCA by only applying SVD on $X$, without calculating $X^T X$.