An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: Principal Component Analysis

The discipline of statistics is based on the idea of analyzing data. In large data sets it is usually the case that one wants to understand the relationships between the different data in the set. This can be difficult to do when the data set is large and it is impossible to visually examine the data for patterns. Principal Component Analysis (PCA) is a tool for identifying and representing underlying patterns in large data sets, and PCA has been called one of the most important and valuable linear algebra tools for statistical analysis. PCA is used to transform a collection of variables into a (usually smaller) number of uncorrelated variables called principal components. The principal components form the most meaningful basis from which to view data by removing extraneous information and revealing underlying relationships in the data. This presents a framework for how to reduce a complex data set to a lower dimension while retaining the important attributes of the data set. The output helps the experimenter determine which dynamics in the data are important and which can be ignored.

Subsection Introduction

In Section 15 we learned that any two bases for a subspace of \(\R^n\) contain the same number of vectors. This allowed us to define the dimension of a subspace of \(\R^n\text{.}\) In this section we extend the arguments we made in Section 15 to arbitrary vector spaces and define the dimension of a vector space.

Subsection Finite Dimensional Vector Spaces

Theorem 33.1 shows that if sets \(\CB_1\) and \(\CB_2\) are finite bases for a vector space \(V\text{,}\) which are linearly independent by definition, then each cannot contain more elements than the other, so the number of elements in each basis must be equal.

Theorem 33.2 states that if a vector space \(V\) has a basis with a finite number of vectors, then the number of vectors in a basis for that vector space is a well-defined number. In other words, the number of vectors in a basis is an invariant of the vector space. This important number is given a name.

We denote the dimension of a finite dimensional vector space \(V\) by \(\dim(V)\text{.}\)

Not every vector space is finite dimensional. We have seen, for example, that the vector space \(\pol\) of all polynomials, regardless of degree, is not a finite-dimensional vector space. In fact, the polynomials

are linearly independent, so \(\pol\) has an infinite linearly independent set and therefore has no finite basis. A vector space that has an infinite basis is called an infinite dimensional vector space.

Finding the dimension of a finite-dimensional vector space amounts to finding a basis for the space.

Subsection The Dimension of a Subspace

Every subspace of a finite-dimensional vector space is a vector space, and since a subspace is contained in a vector space it is natural to think that the dimension of a subspace should be less than or equal to the dimension of the larger vector space. We verify that fact in this section.

Subsection Conditions for a Basis of a Vector Space

There are two items we need to confirm before we can state that a subset \(\CB\) of a subspace \(W\) of a vector space is a basis for \(W\text{:}\) the set \(\CB\) must be linearly independent and span \(W\text{.}\) We can reduce the amount of work it takes to show that a set is a basis if we know the dimension of the vector space in advance.

The result of Activity 33.5 is summarized in the following theorem (compare to Theorem 15.4).

Subsection Examples

What follows are worked examples that use the concepts from this section.

Subsection Summary

• A finite dimensional vector space is a vector space that can be spanned by a finite set of vectors.

• We showed that any two bases for a finite dimensional vector space must contain the same number of vectors. Therefore, we can define the dimension of a finite dimensional vector space \(V\) to be the number of vectors in any basis for \(V\text{.}\)

• If \(V\) is a vector space with dimension \(n\) and \(S\) is any linearly independent subset of \(V\) with \(n\) vectors, then \(S\) is a basis for \(V\text{.}\) Otherwise, we could add vectors to \(S\) to make a basis for \(V\) and then \(V\) would have a basis of more than \(n\) vectors.

• If \(V\) is a vector space with dimension \(n\) and \(S\) is any subset of \(V\) with \(n\) vectors that spans \(V\text{,}\) then \(S\) is a basis for \(V\text{.}\) Otherwise, we could remove vectors from \(S\) to obtain a basis for \(V\) and then \(V\) would have a basis of fewer than \(n\) vectors.

• For any finite dimensional space \(V\) and a subspace \(W\) of \(V\text{,}\) \(\dim(W)\leq \dim(V)\text{.}\)

Subsection Project: Understanding Principal Component Analysis

Suppose we were to film an experiment involving a ball that is bouncing up and down. Naively, we set up several cameras to follow the process of the experiment from different perspectives and collect the data. All of this data tells us something about the bouncing ball, but there may be no perspective that tells us an important piece of information — the axis along which the ball bounces. The question, then, is how we can extract from the data this important piece of information. Principal Component Analysis (PCA) is a tool for just this type of analysis.

We will use an example to illustrate important concepts we will need. To realistically apply PCA we will have much more data than this, but for now we will restrict ourselves to only two variables so that we can visualize our results. Table 33.7 presents information from ten states on two attributes related to the SAT — Evidence-Based Reading and Writing (EBRW) score and Math score. The SAT is made up of three sections: Reading, Writing and Language (also just called Writing), and Math. The The EBRW score is calculated by combining the Reading and Writing section scores — both the Math and EBRW are scored on a scale of 200-800.

Each attribute (Math, EBRW score) creates a vector whose entries are the student responses for that attribute. The data provides the average scores from participating students in each state. In this example we have two attribute vectors:

These vectors form the rows of a \(2 \times 10\) matrix

that makes up our data set. A plot of the data is shown at left in Figure 33.8, where the EBRW score is along the horizontal axis and the math score is along the vertical axis.

The question we want to answer is, how do we represent our data set so that the most important features in the data set are revealed?

A plot of the centered data for our SAT data is shown at right in Figure 33.8. Later we will see why centering the data is useful — it will more easily allow us to project onto subspaces. The goal of PCA is to find a matrix \(P\) so that \(PX = Y\text{,}\) and \(Y\) is suitably transformed to identify the important aspects of the data. We will discuss what the important aspects are shortly. Before we do so, we need to discuss a way to compare the one dimensional data vectors \(\vx_1\) and \(\vx_2\text{.}\)

Recall that the goal of PCA is to find a matrix \(P\) such that \(PX = Y\) where \(P\) transforms the data set to a coordinate system in which the important aspects of the data are revealed. We are now in a position to discuss what that means.

An ideal view of our data would be one in which we can see the direction of greatest variance and one that minimizes redundancy. With redundant data the variables are not independent — that is, covariance is nonzero. So we would like the covariances to all be zero (or as close to zero as possible) to remove redundancy in our data. That means that we would like a covariance matrix in which the non-diagonal entries are all zero. This will be possible if the covariance matrix is diagonalizable.

For our purposes, we want to diagonalize \(XX^{\tr}\) with \(PXX^{\tr}P^{-1}\text{,}\) so the matrix \(P\) that serve our purposes is the one whose rows are the eigenvectors of \(XX^{\tr}\text{.}\) To understand why this matrix is the one we want, recall that we want to have \(PX = Y\text{,}\) and we want to diagonalize \(XX^{\tr}\) to a diagonal covariance matrix \(YY^{\tr}\text{.}\) In this situation we will have (recalling that \(P^{-1}=P^{\tr}\))

So the matrix \(P\) that we want is exactly the one that diagonalizes \(XX^{\tr}\text{.}\)

Project Activity 33.9.

There are two useful ways we can interpret the results of our work so far. An eigenvector of \(XX^{\tr}\) that corresponds to the largest (also called the dominant) eigenvalue \(\lambda_1\) is \([0.66 \ 0.76]^{\tr}\text{.}\) A plot of the centered data along with the eigenspace \(E_{\lambda_1}\) of \(XX^{\tr}\) spanned by \(\vv_1 = [0.66 \ 0.76]^{\tr}\) is shown at left in Figure 33.9. The eigenvector \(\vv_1\) is called the first principal component of \(X\text{.}\) Notice that this line \(E_{\lambda_1}\) indicates the direction of greatest variation in the data. That is, the sum of the squares of the differences between the data points and the mean is as large as possible in this direction. In other words, when we project the data points onto \(E_{\lambda_1}\text{,}\) as shown at right in Figure 33.9, the variation of the resulting points is larger than it is for any other line. In other words, the data is most spread out in this direction.

(a)

There is another way we can interpret this result. If we drop a perpendicular from one of our data points to the space \(E_{\lambda_1}\) it creates a right triangle with sides of length \(a\text{,}\) \(b\text{,}\) and \(c\) as illustrated in the middle of Figure 33.9. Use this idea to explain why maximizing the variation also minimizes the sum of the squares of the distances from the data points to this line. As a result, we have projected our two-dimensional data onto the one-dimensional space that maximizes the variance of the data.

(b)

Recall that the matrix (to two decimal places) \(P = \left[ \begin{array}{rr} - 0.66\amp -0.76\\ 0.76\amp 0.66 \end{array} \right]\) transforms the data set \(X\) to a new data set \(Y=PX\) whose covariance matrix is diagonal. Explain how the \(x\)-axis is related to the transformed data set \(Y\text{.}\)

The result of Project Activity 33.9 is that we have reduced the problem from considering the data in a two-dimensional space to a one-dimensional space \(E_{\lambda_1}\) where the most important aspect of the data is revealed. Of course, we eliminate some of the characteristics of the data, but the most important aspect is still included and highlighted. This is one of the important uses of PCA, data dimension reduction, which allows us to reveal key relationships between the variables that might not be evident when looking at a large dataset.

The second eigenvector of \(XX^{\tr}\) also has meaning. A picture of the eigenspace \(E_{\lambda_2}\) corresponding to the smaller eigenvector \(\lambda_2\) of \(XX^{\tr}\) is shown in Figure 33.11. The second eigenvector of \(XX^{\tr}\) is orthogonal to the first, and the direction of the second eigenvector tells us the direction of the second most amount of variance as can be seen in Figure 33.11.

To summarize, the unit eigenvector for the largest eigenvalue of \(XX^{\tr}\) indicates the direction in which the data has the greatest variance. The direction of the unit eigenvector for the smaller eigenvalue shows the direction in which the data has the second largest variance. This direction is also perpendicular to the first (indicating \(0\) covariance). The directions of the eigenvectors are called the principal components of \(X\text{.}\) The eigenvector with the highest eigenvalue is the first principal component of the data set and the other eigenvectors are ordered by the eigenvalues, highest to lowest. The principal components provide a new coordinate system from which to view our data — one in which we can see the maximum variance and in which there is zero covariance.

In general, PCA is most useful for larger data sets. The process is the same.

• Start with a set of data that forms the rows of an \(m \times n\) matrix. We center the data by subtracting the mean of each row from the entries of that row to create a centered data set in a matrix \(X\text{.}\)

• The principal components of \(X\) are the eigenvectors of \(XX^{\tr}\text{,}\) ordered so that they correspond to the eigenvalues of \(XX^{\tr}\) in decreasing order.

• Let \(P\) be the matrix whose rows are the principal components of \(X\text{,}\) ordered from highest to lowest. Then \(Y = PX\) is suitably transformed to identify the important aspects of the data.

• If \(\lambda_1\text{,}\) \(\lambda_2\text{,}\) \(\ldots\text{,}\) \(\lambda_n\) are the eigenvalues of \(XX^{\tr}\) in decreasing order, then the amount of variance in the data accounted for by the first \(r\) principal components is given by

  \begin{equation*} \frac{\lambda_1+\lambda_2 + \cdots + \lambda_r}{\lambda_1+\lambda_2 + \cdots + \lambda_n}\text{.} \end{equation*}

• The first \(r\) rows of \(Y=PX\) provide the projection of the data set \(X\) onto an \(r\)-dimensional space spanned by the first \(r\) principal components of \(X\text{.}\)

We conclude with a comment. A reasonable question to ask is how we interpret the principal components. Let \(P\) be an orthogonal matrix such that \(PCP^{\tr}\) is the diagonal matrix with the eigenvalues of \(C\) along the diagonal, in decreasing order. We then have the new perspective \(Y = PX\) from which to view the data. The first principal component \(\vp_1\) (the first row of \(P\)) determines the new variable \(\vy_1 = [y_i]\) (the first row of \(Y\)) in the following manner. Let \(\vp_1 = [p_i]^{\tr}\) and let \(\vc_i\) represent the columns of \(X\) so that \(X = [\vc_1 \ \vc_2 \ \vc_3 \ \cdots \ \vc_{20}]\text{.}\) Recognizing that

we have that

That is,

So each \(y_i\) is a linear combination of the original variables (contained in the \(\vc_i\)) with weights from the first principal component. The other new variables are obtained in the same way from the remaining principal components. So even though the principal components may not have an easy interpretation in context, they are connected to the original data in this way. By reducing the data to a few important principal components — that is, visualizing the data in a subspace of small dimension — we can account for almost all of the variation in the data and relate that information back to the original data.