31.1. Projection on a line via variance maximization

Consider a data set of [latex]n[/latex] points [latex]x_j[/latex], [latex]j = 1, \cdots, n[/latex] in [latex]\mathbb{R}^m[/latex]. We can represent this data set as a [latex]m \times n[/latex] matrix [latex]X = [x_1, \cdots, x_n][/latex], where each [latex]x_j[/latex] is a [latex]n[/latex]-vector. The goal of the variance maximization problem is to find a direction [latex]u \in \mathbb{R}^m[/latex] such that the sample variance of the corresponding vector [latex]u^TX = (u^Tx_1, \cdots, u^Tx_n)[/latex] is maximal.

Recall that when [latex]u[/latex] is normalized, the scalar [latex]u^Tx[/latex] is the component of [latex]x[/latex] along [latex]u[/latex], that is, it corresponds to the projection of [latex]x[/latex] on the line passing through [latex]0[/latex] and with direction [latex]u[/latex].

Here, we seek a (normalized) direction [latex]u[/latex] such that the empirical variance of the projected values [latex]u^Tx_j[/latex], [latex]j = 1, \cdots, n[/latex], is large. If [latex]\hat{x}[/latex] is the vector of averages of the [latex]x_j[/latex]‘s, then the average of the projected values is [latex]u^T\hat{x}[/latex]. Thus, the direction of maximal variance is one that solves the optimization problem

[latex]\begin{align*} \max\limits_{u: ||u||_2=1} \frac{1}{n} \sum\limits_{j=1}^n \left((x_j-\hat{x})^Tu\right)^2. \end{align*}[/latex]

The above problem can be formulated as

[latex]\begin{align*} \max\limits_{u: ||u||_2=1} u^T {\textstyle \Sigma} u, \end{align*}[/latex]

where

[latex]\begin{align*} {\textstyle \Sigma} := \frac{1}{n}\sum\limits_{j=1}^n (x_j - \hat{x}) (x_j-\hat{x})^T \end{align*}[/latex]

is the [latex]m \times m[/latex] sample covariance matrix of the data.

We have seen the above problem before, under the name of the Rayleigh quotient of a symmetric matrix. Solving the problem entails simply finding an eigenvector of the covariance matrix [latex]\sum[/latex] that corresponds to the largest eigenvalue.

Maximal variance direction for the Senate voting data. This image shows the scores assigned to each Senator along the direction of maximal variance, [latex]u^T_{\max}(x_j-\hat{x})[/latex], [latex]j = 1, \cdots, n[/latex], with [latex]u_{\max}[/latex] a normalized eigenvector corresponding to the largest eigenvalue of the covariance matrix [latex]\sum[/latex]. Republican Senators tend to score negatively, while we find many Democrats on the positive score (obviously the sign themselves don’t count here, as we could switch [latex]u[/latex] to [latex]-u[/latex]; only the order is important). Hence the direction could be interpreted as revealing the party affiliation. The two Senators that are in the opposite group (especially Sen. Chaffee) have indeed sometimes voted against their party.

Note that the largest absolute score obtained in this plot is about 18 times bigger than that observed on the projection on a random direction. This is consistent with the fact that the current direction has a maximal variance.

31.2. Principal component analysis

Main idea

The main idea behind principal component analysis is to first find a direction that corresponds to maximal variance between the data points. The data is then projected on the hyperplane orthogonal to that direction. We obtain a new data set and find a new direction of maximal variance. We may stop the process when we have collected enough directions (say, three if we want to visualize the data in 3D).

It turns out that the directions found in this way are precisely the eigenvectors of the data’s covariance matrix. The term principal components refers to the directions given by these eigenvectors. Mathematically, the process thus amounts to finding the eigenvalue decomposition of a positive semi-definite matrix, the covariance matrix of the data points.

Projection on a plane

The projection used to obtain, say, a two-dimensional view with the largest variance, is of the form [latex]x \rightarrow Px[/latex], where [latex]P=[u_1, u_2]^T[/latex] is a matrix that contains the eigenvectors corresponding to the first two eigenvalues.

Two-dimensional projection of the Senate voting matrix: This particular planar projection uses the two eigenvectors corresponding to the largest two eigenvalues of the data’s covariance matrix. It seems to allow to cluster of the Senators along party lines and is therefore more informative than, say, the plane corresponding to the two smallest eigenvalues.

31.3. Explained variance

The total variance in the data is defined as the sum of the variances of the individual components. This quantity is simply the trace of the covariance matrix since the diagonal elements of the latter contain the variances. If [latex]\Sigma[/latex] has the EVD [latex]\Sigma = U \Lambda U^T[/latex], where [latex]\Lambda = {\bf diag}(\lambda_1, \cdots, \lambda_n)[/latex] contains the eigenvalues, and [latex]U[/latex] an orthogonal matrix of eigenvectors, then to total variance can be expressed as the sum of all the eigenvalues:

[latex]\begin{align*} {\bf Tr} \Sigma = {\bf Tr}(U\Lambda U^T) = {\bf Tr} (U^TU\Lambda) = {\bf Tr} \Lambda = \lambda_1 + \cdots + \lambda_n. \end{align*}[/latex]

When we project the data on a two-dimensional plane corresponding to the eigenvectors [latex]u_1, u_2[/latex] associated with the two largest eigenvalues [latex]\lambda_1, \lambda_2[/latex], we get a new covariance matrix [latex]P \Sigma P^T[/latex], where [latex]P = [u_1,  u_2]^T[/latex] the total variance of the projected data is

[latex]\begin{align*} {\bf Tr}(P\Sigma P^T) = \lambda_1 + \lambda_2. \end{align*}[/latex]

Hence, we can define the ratio of variance ‘‘explained’’ by the projected data as the ratio:

[latex]\begin{align*} \frac{\lambda_1 + \lambda_2}{\lambda_1 + \cdots + \lambda_n}. \end{align*}[/latex]

If the ratio is high, we can say that much of the variation in the data can be observed on the projected plane.

This image shows the eigenvalues of the [latex]m \times m[/latex] covariance matrix of the Senate voting data, which contains the covariances between the votes of each pair of Senators. Clearly, the eigenvalues decrease very fast. One is tempted to say that In this case, the ratio of explained to total variance is almost [latex]90%[/latex], which indicates that ‘‘most of the information’’ is contained in the first eigenvalue. Since the corresponding eigenvector almost corresponds to a perfect ‘‘party line’’, we can say that party affiliation explains most of the variance in the Senate voting data.