PCA

Principal Component Analysis, or the discrete Karhunen–Loeve transform KLT, is a technique with two important applications in data analysis:

• it “orders” the data in a vector distribution so as to maximize its variance and, using this information, reduce the dimensionality of the problem; it is therefore a lossy data-compression technique, or alternatively a technique for representing the same amount of information with fewer data;
• it transforms the input data so that the covariance matrix of the output data is diagonal and the data components are therefore uncorrelated.

There are likewise two formulations of the PCA definition:

• it projects the data onto a lower-dimensional space such that the variance of the projected data is maximized;
• it projects the data onto a lower-dimensional space such that the distance between the point and its projection is minimized.

A practical example of reducing the dimensionality of a problem is the equation of a hyperplane in $d$ dimensions: there exists a basis of the space that transforms the plane equation, reducing it to $d-1$ dimensions without losing information, thereby reducing the dimensionality of the problem by one.

Figure 2.2: Principal Components.

Let $\mathbf{x}_i \in \mathbb{R}^{d}$ random vectors represent the results of an experiment, that is, realizations of a zero-mean random variable. They can be stored in the rows^2.2 of the matrix $\mathbf{X}$ of dimensions $d \times n$. Thus, the matrix stores $n$ random vectors of dimensionality $d$ with $n > d$. Each row corresponds to a different result $\mathbf {x}$, and the distribution of these experiments must have zero mean, at least empirically.

Assuming that the points have zero mean (which can always be achieved simply by subtracting the centroid), the covariance of the occurrences of $\mathbf {x}$ is given by

$$\boldsymbol\Sigma = E(\mathbf{x} \mathbf{x}^{\top}) \approx \frac{1}{n} \mathbf{X}^{\top} \mathbf{X}$$ (2.69)

If the input data $\mathbf {x}$ are correlated, the covariance matrix $\boldsymbol\Sigma$ is not diagonal.

The goal of PCA is to find an optimal transformation $\mathbf{V}$ that transforms correlated data into uncorrelated data

$$\mathbf{y} = \mathbf{V}^{\top} \mathbf{x}$$ (2.70)

and orders them according to their information content so that, if a subset of the bases is selected, the approach can reduce the dimensionality of the problem.

If there exists an orthonormal basis $\mathbf{V}$ such that the covariance matrix of $\boldsymbol\Sigma_X$ expressed in this basis is diagonal, then the axes of this new basis are called the principal components of $\boldsymbol\Sigma$ (or of the distribution of $X$). When a covariance matrix has all its elements equal to $0$ except on the diagonal, this means that the events are uncorrelated in this new basis of the space.

This transformation can be found by solving an eigenvalue problem: it can be shown that the elements of the diagonal correlation matrix must be the eigenvalues of $\Sigma_X$, and for this reason the variances of the projection of vector $\mathbf {x}$ onto the principal components are the eigenvalues themselves:

$$\boldsymbol \Sigma \mathbf{V} = \mathbf{V} \boldsymbol \Delta$$ (2.71)

where $\mathbf{V}$ is the eigenvector matrix (orthogonal matrix $\mathbf{V}\mathbf{V}^{\top}=\mathbf{I}$) and $\boldsymbol \Delta$ is the diagonal matrix of the eigenvalues $\lambda_1 \ge \ldots \ge \lambda_d$.

There are two approaches to obtaining this result. Since $\boldsymbol\Sigma$ is a real, symmetric, positive-definite matrix, it can be decomposed as

$$\boldsymbol\Sigma = \mathbf{V} \boldsymbol\Delta \mathbf{V}^{\top}$$ (2.72)

called the spectral decomposition, where $\mathbf{V}$ is an orthonormal matrix, the right eigenvalues of $\boldsymbol\Sigma$, and $\boldsymbol \Delta$ is the diagonal matrix containing the eigenvalues. Since matrix $\boldsymbol\Sigma$ is positive definite, all its eigenvalues are positive or zero. Right-multiplying equation (2.72) by $\mathbf{V}$ shows that it is exactly the solution to problem (2.71).

This technique, however, requires the explicit computation of $\boldsymbol\Sigma$. Given a rectangular matrix $\mathbf{X}$, the SVD technique makes it possible to find exactly the eigenvalues and eigenvectors of matrix $\mathbf{X}^{\top} \mathbf{X}$, that is, of $\boldsymbol\Sigma$, and is therefore the most efficient and numerically stable technique for obtaining this result. Using the SVD, the event matrix $\mathbf{X}$ can be decomposed so that

$$\mathbf{X} = \mathbf{U} \mathbf{S} \mathbf{V}^{\top}$$

using the Economy/Compact SVD representation, where $\mathbf{U}$ are the left singular vectors, $\mathbf{S}$ are the eigenvalues of $\boldsymbol\Sigma$, and $\mathbf{V}$ are the right singular vectors. It should be noted that, when using the SVD, it is not necessary to compute the covariance matrix $\boldsymbol\Sigma$ explicitly. This matrix can nevertheless be recovered afterward using the equation

$$\boldsymbol\Sigma = \mathbf{X}^{\top}\mathbf{X} = \mathbf{V} \mathbf{S}^{2} \mathbf{V}^{\top}$$ (2.73)

Comparing this relation with the one in equation (2.72) also gives $\boldsymbol\Delta = \mathbf{S}^{2}$.

The properties of eigenvalues should be recalled:

• The eigenvalues of $\mathbf{X}\mathbf{X}^{\top}$ and $\mathbf{X}^{\top} \mathbf{X}$ are the same.
• The singular values are the eigenvalues of matrix $\mathbf{X}^{\top} \mathbf{X}$, that is, the covariance matrix;
• The largest eigenvalues are associated with the direction vectors of maximum variance;

as well as an important property of the SVD

$$\mathbf{x}^{(l)}=\sum_{i=1}^{l} \mathbf{u}_i \sigma_i \mathbf{v}^{\top}_i$$ (2.74)

which is the rank-$l$ approximation closest to $\mathbf{X}$. This fact, together with the intrinsic property of the SVD of returning the singular values of $\mathbf{X}$ in descending order, makes it possible to approximate a matrix by one of lower rank.

By selecting the number of eigenvectors with sufficiently large eigenvalues, it is possible to create an orthonormal basis $m\times n$ of space $\mathbf{\tilde{V}}$ such that $\mathbf{y} \in \mathbb{R}^{m}$ obtained as the projection

$$\mathbf{y} = \mathbf{\tilde{V}}^{\top}\mathbf{x}$$

represents a lower-dimensional space that nevertheless contains most of the information in the system.

Figure 2.3: Example of the first 10 eigenvectors $24 \times 48$ extracted from the Daimler-DB pedestrian dataset

Footnotes

...rows^2.2

In this document, the row convention has been adopted: the literature likewise uses either row-wise or column-wise representations of the data, and consequently the terminology may differ and refer to $\mathbf{U}$ rather than $\mathbf{V}$, and vice versa.