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.

Similarly, there are two formulations of the PCA definition:

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

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

Figure 2.2: Principal Components.

are stored in the rows^2.2 of the matrix $\mathbf{X}$ of dimensions $n \times d$, a matrix that therefore stores $n$ random vectors of dimensionality $d$ and with $n > d$.

Each row corresponds to a different observation $\mathbf{x}_i$, 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 matrix of the observations 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 decorrelated data

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

and orders them according to their information content so that, by selecting a subset of the bases, the dimensionality of the problem can be reduced.

If there exists an orthonormal basis $\mathbf{V}$ such that the covariance matrix $\boldsymbol\Sigma$ 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 $\mathbf {x}$). When a covariance matrix is obtained whose only nonzero elements are those on the diagonal, the events are mutually uncorrelated in this new basis.

This transformation can be found by solving an eigenvalue problem: it can be shown that the elements of the diagonal matrix are the eigenvalues of $\boldsymbol\Sigma$ and that the variances of the projections of the vector $\mathbf {x}$ onto the principal components coincide with these eigenvalues:

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

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

There are two approaches to obtaining this result.

Since $\boldsymbol\Sigma$ is a real symmetric positive semidefinite 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 the orthonormal eigenvector matrix and $\boldsymbol\Delta$ is the diagonal eigenvalue matrix. Since the matrix $\boldsymbol\Sigma$ is positive semidefinite, all eigenvalues are nonnegative.

This technique, however, requires the explicit computation of $\boldsymbol\Sigma$.

Given a rectangular matrix $\mathbf{X}$, the singular value decomposition (SVD) provides, in a numerically stable manner, the eigenvectors of $\mathbf{X}^{\top}\mathbf{X}$ and, through the squares of the singular values, the corresponding eigenvalues. The SVD is therefore the standard technique for computing principal components.

Using the SVD, the event matrix $\mathbf{X}$ can be decomposed as

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

using the Economy/Compact SVD representation, where $\mathbf{U}$ contains the left singular vectors (left singular vectors), $\mathbf{S}$ contains the singular values of $\mathbf{X}$, and $\mathbf{V}$ contains 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 subsequently be obtained from

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

Comparing this relation with equation (2.72) gives

$$\boldsymbol\Delta = \frac{1}{n}\mathbf{S}^{2}.$$ (2.74)

The following properties of eigenvalues and singular values should be recalled:

• The matrices $\mathbf{X}\mathbf{X}^{\top}$ and $\mathbf{X}^{\top}\mathbf{X}$ share the same nonzero eigenvalues.
• The singular values $\sigma_i$ of the matrix $\mathbf{X}$ are the square roots of the eigenvalues of $\mathbf{X}^{\top}\mathbf{X}$:
  
  $$\sigma_i = \sqrt{\lambda_i(\mathbf{X}^{\top}\mathbf{X})}.$$
  
  

• The largest eigenvalues of the covariance matrix are associated with the directions of maximum data variance.

An important property of the SVD should also be recalled:

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

which represents the best rank-$l$ approximation of the matrix $\mathbf{X}$ in the Frobenius-norm sense. This fact, together with the property of the SVD that it returns the singular values in descending order, makes it possible to approximate a matrix with one of lower rank.

By selecting the eigenvectors associated with the largest eigenvalues, it is possible to construct a matrix

$$\tilde{\mathbf V} \in \mathbb{R}^{d\times m}$$

whose columns form an orthonormal basis of the reduced space. The projection of a vector

$$\mathbf x \in \mathbb{R}^{d}$$

onto this subspace is

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

with

$$\mathbf y \in \mathbb{R}^{m}.$$

The vector $\mathbf y$ represents a reduced-dimensionality description of the data that preserves most of the variance present 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 uses both row-wise and column-wise representations of data, and consequently the terminology may differ and refer to $\mathbf{U}$ rather than $\mathbf{V}$, and vice versa.