Principal Component Analysis

Learning Objectives

After reading this page, you should be able to:

  1. Project a vector onto a subspace.
  2. Prove that minimizing reconstruction error is equivalent to maximizing the variance of the reconstructions.
  3. Perform all the steps of principal component analysis on a given dataset.
  4. Explain whether PCA is suitable for solving a given problem based on the properties of PCA.

1 Introduction

Real-world data often has many features, and such high-dimensional data is hard to visualize, analyze, or model. We would like to find a lower-dimensional representation of the data that still preserves most of its information. This process is called dimensionality reduction. Reducing the number of dimensions lets us visualize complex data, extract meaningful patterns or features, and compress data with minimal information loss.

Several techniques can reduce the dimensionality of data, and each one finds a lower-dimensional representation in a different way. Autoencoders use a neural network to compress each data point into a short code and then reconstruct the input from that code. Matrix factorization approximates a large data matrix as the product of two smaller matrices, which is useful in applications such as recommender systems. In this page, we focus on principal component analysis (PCA), one of the most widely used techniques. PCA finds the few directions along which the data spreads out the most and describes each data point using only those directions. PCA and matrix factorization are linear techniques, while autoencoders are non-linear and can capture curved structure in the data, such as the Swiss roll in Figure 1 below.

Figure 1: Interactive A Swiss roll is a two-dimensional sheet rolled up in three dimensions. Non-linear dimensionality reduction methods such as Isomap recover the flat sheet. Press Unroll or drag the slider to unroll the sheet. Drag the 3D plot to rotate it. Hover over a point to highlight it in both plots. The colours show that points close together on the sheet stay close together after unrolling.

2 Projecting Data onto a Subspace

In many data sets, the features are related to each other, so the data does not spread out equally in every direction. Imagine a cloud of points in three dimensions shaped like a slightly thick pancake. The points spread out a lot along two directions, the length and width of the pancake, but barely at all along the third direction, its thickness. If we flatten the pancake onto a plane, each point moves only a little, so we lose very little information. In return, we need only two numbers instead of three to describe each point. Flattening the data like this is called a projection onto a subspace. You can think of a projection as looking at the data from a particular direction, like a shadow cast onto a wall. The key question is which subspace to project onto. A good choice keeps the directions along which the data spreads out the most, and PCA gives us a way to find them.

Figure 2: Interactive A three-dimensional data set shaped like a pancake. Drag the plot to rotate it. Check Show plane to see the plane that PCA finds, and check Show projections to connect each data point to its projection onto the plane. Press Face-On View to see how much the data spreads out within the plane. Press Edge-On View to see how little the data spreads out in the direction perpendicular to the plane.

2.1 Projecting Two-Dimensional Vector onto One-Dimensional Subspace

Let’s start with the simplest case. Suppose that we have some two-dimensional data and want to project each data point onto a one-dimensional subspace.

We start by defining a one-dimensional subspace.

Definition: A one-dimensional subspace \(S\) is defined by a unit vector \(\mathbf{u}\) (a vector of length one). The subspace \(S\) is the line through the origin along \(\mathbf{u}\), and it contains every scalar multiple of \(\mathbf{u}\), \[ S = \{\, z\mathbf{u} \mid z \in \mathbb{R} \,\}. \]

You can think of \(z\) as a coordinate along the line. Its magnitude tells us how far the point is from the origin, and its sign tells us the direction.

For example, we can define the one-dimensional subspace for the line \(x_2 = x_1\) in Figure 3 as

\[ S = \left\{\, \begin{bmatrix} \tfrac{z}{\sqrt{2}} \\ \tfrac{z}{\sqrt{2}} \end{bmatrix} \,\middle|\, z \in \mathbb{R} \,\right\}, \]

with the unit vector

\[ \mathbf{u} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ \tfrac{1}{\sqrt{2}} \end{bmatrix}. \]

Figure 3: A one-dimensional subspace \(S\) defined by the unit vector \(\mathbf{u}\).

Question: Consider the line through the origin and the point

\[ \begin{bmatrix} 3 & 4 \end{bmatrix}^\top. \]

Write down the definition of this line as a one-dimensional subspace \(S\).

Answer: The subspace is

\[ S = \left\{\, \begin{bmatrix} \tfrac{3z}{5} & \tfrac{4z}{5} \end{bmatrix}^\top \,\middle|\, z \in \mathbb{R} \,\right\}, \]

with the unit vector

\[ \mathbf{u} = \begin{bmatrix} \tfrac{3}{5} & \tfrac{4}{5} \end{bmatrix}^\top. \]

To find \(\mathbf{u}\), we divide the vector from the origin to the given point by its length, which is

\[ \sqrt{3^2 + 4^2} = 5. \]

The unit vector pointing the other way, \[ -\mathbf{u} = \begin{bmatrix} -\tfrac{3}{5} & -\tfrac{4}{5} \end{bmatrix}^\top, \] defines the same subspace, so it is also a correct answer.

Next, let’s define a point in the 2-dimensional data space and project this point onto the one-dimensional subspace.

Definition: Let \(\mathbf{x} \in \mathbb{R}^2\) be a data point and \(S\) be a one-dimensional subspace of \(\mathbb{R}^2\). The orthogonal projection of \(\mathbf{x}\) onto \(S\), written \(\hat{\mathbf{x}}\), is the unique point in \(S\) with the smallest Euclidean distance to \(\mathbf{x}\),

\[ \hat{\mathbf{x}} = \operatorname*{arg\,min}_{\mathbf{v} \in S} \, \|\mathbf{x} - \mathbf{v}\|. \]

See Figure 4 for an example of projecting the vector \(\begin{bmatrix} 2 & 1 \end{bmatrix}^\top\) onto the subspace \(S\) to get the vector \(\begin{bmatrix} \tfrac{3}{2} & \tfrac{3}{2} \end{bmatrix}^\top\). Intuitively, the projection \(\hat{\mathbf{x}}\) is the shadow that \(\mathbf{x}\) casts on \(S\) when light shines onto the line from a direction perpendicular to it.

Figure 4: Projecting the data point \(\mathbf{x}\) onto the one-dimensional subspace \(S\) defined by the unit vector \(\mathbf{u}\). The dashed segment from \(\mathbf{x}\) to \(\hat{\mathbf{x}}\) is perpendicular to \(S\).

Although the definition above provides a nice intuition, it doesn’t tell us how to derive the projection. For this case, a simple derivation gives us the following formulas of computing the projection.

Definition: Let \(\mathbf{x} \in \mathbb{R}^2\) and let \(S\) be the one-dimensional subspace defined by the unit vector \(\mathbf{u}\).

The representation or code of \(\mathbf{x}\) in \(S\) is the scalar \[ z = \mathbf{x}^\top \mathbf{u}. \]

The reconstruction or orthogonal projection of \(\mathbf{x}\) is the vector \[ \hat{\mathbf{x}} = z\mathbf{u} = (\mathbf{x}^\top \mathbf{u})\,\mathbf{u}, \]

Intuitively, \(z\) tells us the (signed) magnitude of the projection, and the unit vector \(\mathbf{u}\) gives its direction. The names describe what each quantity does. One number \(z\) is enough to represent \(\mathbf{x}\) within \(S\), and \(\hat{\mathbf{x}}\) is our best attempt to reconstruct \(\mathbf{x}\) from that \(z\).

Let’s apply these formulas to the vector \(\begin{bmatrix} 2 & 1 \end{bmatrix}^\top\) in Figure 4 and verify its projection. The data point is \[ \mathbf{x} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}. \] Its representation is \[ z = \mathbf{x}^\top \mathbf{u} = \begin{bmatrix} 2 & 1 \end{bmatrix} \begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ \tfrac{1}{\sqrt{2}} \end{bmatrix} = \tfrac{2}{\sqrt{2}} + \tfrac{1}{\sqrt{2}} = \tfrac{3}{\sqrt{2}}, \]

and its reconstruction is

\[ \hat{\mathbf{x}} = \tfrac{3}{\sqrt{2}} \begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ \tfrac{1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} \tfrac{3}{2} \\ \tfrac{3}{2} \end{bmatrix}. \]

Question: Consider the one-dimensional subspace \(S\) for the line through the origin and the point \(\mathbf{a}\). Determine the orthogonal projection of the data point \(\mathbf{x}\) onto \(S\). Then, on Figure 5, draw the subspace \(S\) and the projection \(\hat{\mathbf{x}}\).

\[\mathbf{a} = \begin{bmatrix} 2 \\ -1 \end{bmatrix} \qquad \qquad \mathbf{x} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}\]

Figure 5: The point \(\mathbf{a}\) on the line and the data point \(\mathbf{x}\).

Answer: The vector \(\mathbf{a}\) points along the line, but it is not a unit vector because its length is

\[ \|\mathbf{a}\| = \sqrt{2^2 + (-1)^2} = \sqrt{5}. \]

Dividing \(\mathbf{a}\) by its length gives the unit vector

\[ \mathbf{u} = \frac{\mathbf{a}}{\|\mathbf{a}\|} = \begin{bmatrix} \tfrac{2}{\sqrt{5}} \\ -\tfrac{1}{\sqrt{5}} \end{bmatrix}, \]

so the subspace is

\[ S = \left\{\, z \begin{bmatrix} \tfrac{2}{\sqrt{5}} \\ -\tfrac{1}{\sqrt{5}} \end{bmatrix} \,\middle|\, z \in \mathbb{R} \,\right\}. \]

The representation of \(\mathbf{x}\) is

\[ z = \mathbf{x}^\top \mathbf{u} = \begin{bmatrix} 2 & 1 \end{bmatrix} \begin{bmatrix} \tfrac{2}{\sqrt{5}} \\ -\tfrac{1}{\sqrt{5}} \end{bmatrix} = \tfrac{4}{\sqrt{5}} - \tfrac{1}{\sqrt{5}} = \tfrac{3}{\sqrt{5}}, \]

and its reconstruction is

\[ \hat{\mathbf{x}} = \tfrac{3}{\sqrt{5}} \begin{bmatrix} \tfrac{2}{\sqrt{5}} \\ -\tfrac{1}{\sqrt{5}} \end{bmatrix} = \begin{bmatrix} \tfrac{6}{5} \\ -\tfrac{3}{5} \end{bmatrix}. \]

Figure 6 shows the subspace \(S\) and the projection \(\hat{\mathbf{x}}\).

Figure 6: The subspace \(S\) through the origin and \(\mathbf{a}\), defined by the unit vector \(\mathbf{u}\), and the projection \(\hat{\mathbf{x}}\) of the data point \(\mathbf{x}\) onto \(S\).

An alternative solution is to choose \(-\mathbf{u}\) as the unit vector, and you will get the representation \(z = -\tfrac{3}{\sqrt{5}}\) and the same reconstruction \(\hat{\mathbf{x}}\).

2.2 Projecting D-Dimensional Vector onto K-Dimensional Subspace

Now, let’s generalize our formulas to a larger number of dimensions. Consider data in \(D\)-dimensional space and a subspace with \(K\) dimensions, where \(K < D\). We start by defining a \(K\)-dimensional subspace.

Definition: A \(K\)-dimensional subspace \(S\) of \(\mathbb{R}^D\) is defined by \(K\) vectors \(\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_K \in \mathbb{R}^D\) that are orthonormal, meaning each vector has length one and every pair of distinct vectors is perpendicular.

The subspace \(S\) contains every linear combination of these vectors, \[ S = \{\, z_1 \mathbf{u}_1 + z_2 \mathbf{u}_2 + \cdots + z_K \mathbf{u}_K \mid z_1, z_2, \dots, z_K \in \mathbb{R} \,\}. \]

We call \(\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_K\) an orthonormal basis for \(S\).

This definition generalizes the one-dimensional case. The unit vectors define \(K\) perpendicular directions. They act like the axes of a coordinate system for \(S\), just like the two axes for the plane. The values \(z_1, z_2, \dots, z_K\) define the signed magnitudes along these directions.

In practice, we often stack the basis vectors as the columns of a matrix \[ \mathbf{U} = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_K \end{bmatrix} \in \mathbb{R}^{D \times K}, \] and collect the coordinates into a vector \[ \mathbf{z} = \begin{bmatrix} z_1 & z_2 & \cdots & z_K \end{bmatrix}^\top \in \mathbb{R}^K. \] With this notation, every vector in \(S\) can be expressed as the following matrix-vector product \[ \mathbf{U}\mathbf{z} = z_1 \mathbf{u}_1 + z_2 \mathbf{u}_2 + \cdots + z_K \mathbf{u}_K. \]

Now we can project a data point \(\mathbf{x} \in \mathbb{R}^D\) onto \(S\). The formulas look just like the one-dimensional case, with the matrix \(\mathbf{U}\) taking the place of the unit vector \(\mathbf{u}\).

Definition: Let \(\mathbf{x} \in \mathbb{R}^D\) and let \(S\) be the \(K\)-dimensional subspace whose orthonormal basis vectors are the columns of \(\mathbf{U} \in \mathbb{R}^{D \times K}\).

The representation or code of \(\mathbf{x}\) in \(S\) is the vector \[ \mathbf{z} = \mathbf{U}^\top \mathbf{x} \in \mathbb{R}^K. \]

The reconstruction or orthogonal projection of \(\mathbf{x}\) onto \(S\) is the vector \[ \hat{\mathbf{x}} = \mathbf{U}\mathbf{z} = \mathbf{U}\mathbf{U}^\top \mathbf{x} \in \mathbb{R}^D. \]

Let’s apply these formulas to project a three-dimensional data point onto a two-dimensional subspace. Consider \[ \mathbf{x} = \begin{bmatrix} 2 \\ 1 \\ 3 \end{bmatrix}, \qquad \mathbf{U} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} & 0 \\ 0 & 1 \\ \tfrac{1}{\sqrt{2}} & 0 \end{bmatrix}. \] The two columns of \(\mathbf{U}\) each have length one and are perpendicular to each other, so they form an orthonormal basis for a plane \(S\) in \(\mathbb{R}^3\). The representation of \(\mathbf{x}\) is \[ \mathbf{z} = \mathbf{U}^\top \mathbf{x} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} & 0 & \tfrac{1}{\sqrt{2}} \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 2 \\ 1 \\ 3 \end{bmatrix} = \begin{bmatrix} \tfrac{5}{\sqrt{2}} \\ 1 \end{bmatrix}, \] and its reconstruction is \[ \hat{\mathbf{x}} = \mathbf{U}\mathbf{z} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} & 0 \\ 0 & 1 \\ \tfrac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} \tfrac{5}{\sqrt{2}} \\ 1 \end{bmatrix} = \begin{bmatrix} \tfrac{5}{2} \\ 1 \\ \tfrac{5}{2} \end{bmatrix}. \] The code \(\mathbf{z}\) describes \(\mathbf{x}\) with two numbers instead of three.

Figure 7: Interactive Projecting the data point \(\mathbf{x}\) onto the plane \(S\) spanned by the orthonormal basis vectors \(\mathbf{u}_1\) and \(\mathbf{u}_2\). The dashed segment from \(\mathbf{x}\) to its projection \(\hat{\mathbf{x}}\) is perpendicular to \(S\). Drag the plot to rotate it. Press Edge-On View to look along the plane and see that the dashed segment meets \(S\) at a right angle.

Question: Project the same data point \(\mathbf{x}\) onto a different two-dimensional subspace, defined by \[ \mathbf{x} = \begin{bmatrix} 2 \\ 1 \\ 3 \end{bmatrix}, \qquad \mathbf{U} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} & 0 \\ -\tfrac{1}{\sqrt{2}} & 0 \\ 0 & 1 \end{bmatrix}. \] Compute the representation \(\mathbf{z}\) and the reconstruction \(\hat{\mathbf{x}}\).

Answer: The representation of \(\mathbf{x}\) is \[ \mathbf{z} = \mathbf{U}^\top \mathbf{x} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} & -\tfrac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 \\ 1 \\ 3 \end{bmatrix} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ 3 \end{bmatrix}, \] and its reconstruction is \[ \hat{\mathbf{x}} = \mathbf{U}\mathbf{z} = \begin{bmatrix} \tfrac{1}{\sqrt{2}} & 0 \\ -\tfrac{1}{\sqrt{2}} & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \tfrac{1}{\sqrt{2}} \\ 3 \end{bmatrix} = \begin{bmatrix} \tfrac{1}{2} \\ -\tfrac{1}{2} \\ 3 \end{bmatrix}. \]

3 Learning a Good Subspace

Figure 8 shows the same data point \(\mathbf{x}\) projected onto two different one-dimensional subspaces. Which subspace is better?

(A)

(B)

Figure 8: Projecting the same data point \(\mathbf{x}\) onto two different one-dimensional subspaces.

Intuitively, the projection in (A) gives a much better approximation of \(\mathbf{x}\). The subspace in (A) is closer to the original vector in direction. As a result, the projection in (A) is much closer to the original vector in both direction and magnitude, giving us a reconstruction that kept more information of the original vector.

Recall that our overall goal for PCA is to represent data in a lower-dimensional space while losing as little information as possible. Intuitively, we can measure the amount of information in a set of data points through its variance or spread. We can capture this goal in two concrete ways. One, we can choose a subspace that minimizes the information lost by the projection. Two, we can choose a subspace that preserves as much variance in the data as possible. These two objectives look very different on the surface. As you will see below, they are in fact mathematically equivalent.

Let’s make the two objectives more concrete. Suppose that we have a data set of \(N\) data points \(\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \dots, \mathbf{x}^{(N)} \in \mathbb{R}^D,\) and we want to project each data point onto a \(K\)-dimensional subspace \(S\), where \(K < D\). The subspace \(S\) is defined by the orthonormal basis \(\mathbf{U} = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_K \end{bmatrix} \in \mathbb{R}^{D \times K}.\)

Before writing down the objectives, we need to take care of one detail. We care about preserving the variance of the data, which measures how the data spreads out around its mean. However, our subspaces always pass through the origin, so the reconstructions end up capturing the spread around the origin instead, which is not what we want. To fix this, we shift the data so that its mean is at the origin. Let \(\boldsymbol{\mu}\) be the mean of the data points, \[ \boldsymbol{\mu} = \frac{1}{N} \sum_{i=1}^N \mathbf{x}^{(i)}. \]

We centre the data by subtracting the mean from each data point,

\[ \tilde{\mathbf{x}}^{(i)} = \mathbf{x}^{(i)} - \boldsymbol{\mu}, \quad \text{for } i = 1, 2, \dots, N. \]

Centring shifts the whole data set without changing its shape, so the spread of the data stays the same. From now on, we will work with the centred data points \(\tilde{\mathbf{x}}^{(i)}\) and simply call them \(\mathbf{x}^{(i)}\). This means that the data points now have mean \(\boldsymbol{\mu} = \mathbf{0}\). Later, we will see that centring the data is the first step of PCA.

For our first objective, we want to minimize the information lost through the projection. We can quantify the information loss by the reconstruction error, defined as the squared distance between each original vector and its projection. A small reconstruction error means that the subspace \(S\) preserves \(\mathbf{x}\) well.

Definition: Let \(\hat{\mathbf{x}}\) be the reconstruction of a data point \(\mathbf{x}\) in a subspace \(S\). The reconstruction error of \(\mathbf{x}\) is \[ \|\mathbf{x} - \hat{\mathbf{x}}\|^2. \]

Given this definition, we can aim to choose the subspace that minimizes the average reconstruction error over the data set, \[ \min_{\mathbf{U} \,:\, \mathbf{U}^\top \mathbf{U} = \mathbf{I}} \; \frac{1}{N} \sum_{i=1}^N \|\mathbf{x}^{(i)} - \hat{\mathbf{x}}^{(i)}\|^2. \] The constraint \(\mathbf{U}^\top \mathbf{U} = \mathbf{I}\) says that the columns of \(\mathbf{U}\) are orthonormal.

For the second objective, we want to choose the subspace that maximizes the variance of the reconstructions, \[ \max_{\mathbf{U} \,:\, \mathbf{U}^\top \mathbf{U} = \mathbf{I}} \; \frac{1}{N} \sum_{i=1}^N \|\hat{\mathbf{x}}^{(i)} - \boldsymbol{\mu}\|^2. \] Since the data is centred, \(\boldsymbol{\mu} = \mathbf{0}\), and the reconstructions also have mean \(\mathbf{0}\). We keep \(\boldsymbol{\mu}\) in the formula to make it clear that this quantity is a variance.

To show that these two objectives are equivalent, we will show that the sum of the average reconstruction error and the variance of the reconstructions is equal to the variance of the original data points.

Theorem: Let \(\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, \dots, \mathbf{x}^{(N)} \in \mathbb{R}^D\) be centred data points with mean \(\boldsymbol{\mu} = \mathbf{0}\), and let \(\mathbf{U} \in \mathbb{R}^{D \times K}\) have orthonormal columns. For each \(i\), let \(\hat{\mathbf{x}}^{(i)} = \mathbf{U}\mathbf{U}^\top \mathbf{x}^{(i)}\) be the reconstruction of \(\mathbf{x}^{(i)}\). Then \[ \underbrace{\frac{1}{N} \sum_{i=1}^N \|\mathbf{x}^{(i)} - \hat{\mathbf{x}}^{(i)}\|^2}_{\text{average reconstruction error}} + \underbrace{\frac{1}{N} \sum_{i=1}^N \|\hat{\mathbf{x}}^{(i)} - \boldsymbol{\mu}\|^2}_{\text{variance of the reconstructions}} = \underbrace{\frac{1}{N} \sum_{i=1}^N \|\mathbf{x}^{(i)} - \boldsymbol{\mu}\|^2}_{\text{variance of the data}}. \]

The variance of the original data points does not depend on \(\mathbf{U}\), so it is a constant. As a result, minimizing the average reconstruction error over \(\mathbf{U}\) is equivalent to maximizing the variance of the reconstructions over \(\mathbf{U}\).

Question: Prove the theorem above.

Answer: The proof has three steps.

Step 1: The error vector is orthogonal to the reconstruction.

Since \(\hat{\mathbf{x}}^{(i)}\) is the orthogonal projection of \(\mathbf{x}^{(i)}\) onto \(S\), the error vector \(\mathbf{x}^{(i)} - \hat{\mathbf{x}}^{(i)}\) is orthogonal to every vector in \(S\). The reconstruction \(\hat{\mathbf{x}}^{(i)}\) lies in \(S\). Therefore, \(\mathbf{x}^{(i)} - \hat{\mathbf{x}}^{(i)}\) is orthogonal to \(\hat{\mathbf{x}}^{(i)}\), as Figure 9 illustrates.

Figure 9: The error vector \(\mathbf{x} - \hat{\mathbf{x}}\) points from the reconstruction \(\hat{\mathbf{x}}\) to the data point \(\mathbf{x}\). It is orthogonal to \(S\), so it is also orthogonal to \(\hat{\mathbf{x}}\), which lies in \(S\).

We can also verify this algebraically. Let’s drop the superscript for simplicity. We need to show that \[ \hat{\mathbf{x}}^\top (\mathbf{x} - \hat{\mathbf{x}}) = 0 \] First, we substitute the formula \(\hat{\mathbf{x}} = \mathbf{U}\mathbf{U}^\top \mathbf{x}\), \[ \hat{\mathbf{x}}^\top (\mathbf{x} - \hat{\mathbf{x}}) = (\mathbf{U}\mathbf{U}^\top \mathbf{x})^\top (\mathbf{x} - \mathbf{U}\mathbf{U}^\top \mathbf{x}). \] Next, we apply the identity for the transpose of a product, \((\mathbf{A}\mathbf{B})^\top = \mathbf{B}^\top \mathbf{A}^\top,\) which gives \[ (\mathbf{U}\mathbf{U}^\top \mathbf{x})^\top = \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top .\] Substituting this and expanding, we get \[ \begin{aligned} \hat{\mathbf{x}}^\top (\mathbf{x} - \hat{\mathbf{x}}) &= \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top (\mathbf{x} - \mathbf{U}\mathbf{U}^\top \mathbf{x}) \\ &= \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top \mathbf{x} - \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top \mathbf{U}\mathbf{U}^\top \mathbf{x}. \end{aligned} \] Using \(\mathbf{U}^\top \mathbf{U} = \mathbf{I}\), we get \[ \begin{aligned} \hat{\mathbf{x}}^\top (\mathbf{x} - \hat{\mathbf{x}}) &= \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top \mathbf{x} - \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top \mathbf{U}\mathbf{U}^\top \mathbf{x} \\ &= \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top \mathbf{x} - \mathbf{x}^\top \mathbf{U}\mathbf{U}^\top \mathbf{x} \\ &= 0. \end{aligned} \]

Step 2: Apply the Pythagorean theorem.

By Step 1, the vectors \(\hat{\mathbf{x}}^{(i)}\) and \(\mathbf{x}^{(i)} - \hat{\mathbf{x}}^{(i)}\) form the two legs of a right triangle whose hypotenuse is \(\mathbf{x}^{(i)}\). The Pythagorean theorem gives \[ \|\mathbf{x}^{(i)} - \hat{\mathbf{x}}^{(i)}\|^2 + \|\hat{\mathbf{x}}^{(i)}\|^2 = \|\mathbf{x}^{(i)}\|^2. \]

Step 3: Average over the data points.

Averaging this equation over \(i = 1, 2, \dots, N\) gives \[ \frac{1}{N} \sum_{i=1}^N \|\mathbf{x}^{(i)} - \hat{\mathbf{x}}^{(i)}\|^2 + \frac{1}{N} \sum_{i=1}^N \|\hat{\mathbf{x}}^{(i)}\|^2 = \frac{1}{N} \sum_{i=1}^N \|\mathbf{x}^{(i)}\|^2. \] Since the data is centred, this equation is exactly the theorem.

4 Define and Execute PCA

5 Summary