Skip to main content

MATH 345: Linear Algebra and Optimization

Sebastien Roch with Jacob Denson and Kaitlyn Phillipson

Section 6.4 Principal component analysis

A data matrix can have many feature columns. Principal component analysis, or PCA, looks for orthogonal directions that capture as much centered variation as possible. The first direction is found with one constraint: it must have unit length. Each later direction has additional orthogonality constraints.
🔗

Definition 6.4.1. Centered data and covariance matrix.

Let
\begin{equation*} \mathbf{x}_1,\ldots,\mathbf{x}_n\in\R^d \end{equation*}
be data vectors. Their mean is
\begin{equation*} \bar{\mathbf{x}} = \frac1n\sum_{i=1}^n\mathbf{x}_i. \end{equation*}
The centered data vectors are
\begin{equation*} \mathbf{z}_i = \mathbf{x}_i-\bar{\mathbf{x}}. \end{equation*}
Let \(Z\) be the \(n\times d\) matrix whose \(i\)-th row is \(\mathbf{z}_i^T\text{.}\) The covariance matrix is
\begin{align*} C\\ \amp=\frac1n Z^TZ\\ \amp=\frac1n\sum_{i=1}^n \mathbf{z}_i\mathbf{z}_i^T. \end{align*}
🔗
🔗
Some conventions divide by \(n-1\) instead of \(n\text{.}\) This multiplies every covariance eigenvalue by the same positive constant and does not change the eigenvectors.
🔗

Scores and captured variation.

Let \(\mathbf{v}\in\R^d\) be a unit vector. The score of the \(i\)-th centered data point in direction \(\mathbf{v}\) is
\begin{equation*} t_i = \mathbf{v}^T\mathbf{z}_i. \end{equation*}
The score vector is
\begin{equation*} \mathbf{t}=Z\mathbf{v}. \end{equation*}
Its average squared score is
\begin{align*} \frac1n\sum_{i=1}^n t_i^2\\ \amp=\frac1n\|Z\mathbf{v}\|^2\\ \amp=\mathbf{v}^TC\mathbf{v}. \end{align*}
Thus captured variation is a quadratic form.
🔗
The matrix \(C\) is symmetric. Also,
\begin{align*} \mathbf{v}^TC\mathbf{v}\\ \amp=\frac1n\|Z\mathbf{v}\|^2\\ \amp\geq 0 \end{align*}
for every \(\mathbf{v}\text{,}\) so the eigenvalues of \(C\) are nonnegative.
🔗
🔗

Definition 6.4.2. First principal direction.

A first principal direction is a unit vector \(\mathbf{v}_1\) that maximizes
\begin{equation*} \mathbf{v}^TC\mathbf{v} \end{equation*}
subject to
\begin{equation*} \|\mathbf{v}\|=1. \end{equation*}
The entries of
\begin{equation*} \mathbf{t}_1=Z\mathbf{v}_1 \end{equation*}
are the first principal-component scores.
🔗
By Fact 6.3.1, \(\mathbf{v}_1\) may be chosen as a unit eigenvector of \(C\) corresponding to its largest eigenvalue \(\lambda_1\text{.}\) The maximum captured variation is \(\lambda_1\text{.}\)
🔗
🔗

Reconstruction view.

For a unit direction \(\mathbf{v}\text{,}\) the orthogonal projection of \(\mathbf{z}_i\) onto
\begin{equation*} \spans\{\mathbf{v}\} \end{equation*}
is
\begin{equation*} \widehat{\mathbf{z}}_i = t_i\mathbf{v}. \end{equation*}
The corresponding reconstructed data point is
\begin{equation*} \widehat{\mathbf{x}}_i = \bar{\mathbf{x}}+\widehat{\mathbf{z}}_i. \end{equation*}
Define the reconstruction residual by
\begin{equation*} \mathbf{r}_i = \mathbf{z}_i-\widehat{\mathbf{z}}_i. \end{equation*}
By Definition 4.2.6 and Theorem 4.2.8,
\begin{equation*} \mathbf{r}_i\perp\mathbf{v}. \end{equation*}
Therefore
\begin{equation*} \|\mathbf{z}_i\|^2 = t_i^2+\|\mathbf{r}_i\|^2. \end{equation*}
Summing over the data gives
\begin{equation*} \sum_{i=1}^n\|\mathbf{z}_i\|^2 = \sum_{i=1}^n t_i^2 + \sum_{i=1}^n\|\mathbf{r}_i\|^2. \end{equation*}
The quantity on the left does not depend on \(\mathbf{v}\text{.}\) Thus maximizing the total squared scores is equivalent to minimizing the total squared reconstruction residuals.
🔗
🔗

Activity 6.4.3. Principal directions of a small data set (U6-LO5, U5-LO3, U4-LO3).

The rows of
\begin{equation*} X= \begin{bmatrix} 4 \amp 3\\ 3 \amp 4\\ 0 \amp 1\\ 1 \amp 0 \end{bmatrix} \end{equation*}
are four data points in \(\R^2\text{.}\)
🔗
  1. Compute the mean \(\bar{\mathbf{x}}\) and the centered data matrix \(Z\text{.}\)
    🔗
    🔗
  2. Compute
    \begin{equation*} C=\frac14Z^TZ. \end{equation*}
    🔗
    🔗
  3. Find the eigenvalues of \(C\) and an orthonormal basis of eigenvectors. Choose \(\mathbf{v}_1\) for the larger eigenvalue and \(\mathbf{v}_2\) for the smaller eigenvalue.
    🔗
    🔗
  4. Compute the first principal-component score vector
    \begin{equation*} \mathbf{t}_1=Z\mathbf{v}_1. \end{equation*}
    🔗
    🔗
  5. For the first centered point \(\mathbf{z}_1\text{,}\) compute
    \begin{equation*} \widehat{\mathbf{z}}_1 = (\mathbf{v}_1^T\mathbf{z}_1)\mathbf{v}_1 \end{equation*}
    and
    \begin{equation*} \mathbf{r}_1 = \mathbf{z}_1-\widehat{\mathbf{z}}_1. \end{equation*}
    Check that
    \begin{equation*} \mathbf{r}_1\cdot\mathbf{v}_1=0 \end{equation*}
    and
    \begin{equation*} \|\mathbf{z}_1\|^2 = (\mathbf{v}_1^T\mathbf{z}_1)^2+\|\mathbf{r}_1\|^2. \end{equation*}
    🔗
    🔗
  6. Form
    \begin{equation*} V= \begin{bmatrix} \mathbf{v}_1 \amp \mathbf{v}_2 \end{bmatrix} \end{equation*}
    and compute \(V^TCV\text{.}\)
    🔗
    🔗
  7. What fraction of the total centered variation is captured by the first principal direction?
    🔗
    🔗
  8. Describe the affine line
    \begin{equation*} \bar{\mathbf{x}}+\spans\{\mathbf{v}_1\}. \end{equation*}
    🔗
    🔗
Solution.
The mean is
\begin{equation*} \bar{\mathbf{x}} = \begin{bmatrix} 2\\ 2 \end{bmatrix}. \end{equation*}
Therefore
\begin{equation*} Z= \begin{bmatrix} 2 \amp 1\\ 1 \amp 2\\ -2 \amp -1\\ -1 \amp -2 \end{bmatrix}. \end{equation*}
🔗
We calculate
\begin{align*} C\\ \amp=\frac14Z^TZ\\ \amp=\frac14 \begin{bmatrix} 10 \amp 8\\ 8 \amp 10 \end{bmatrix}\\ \amp= \begin{bmatrix} 5/2 \amp 2\\ 2 \amp 5/2 \end{bmatrix}. \end{align*}
🔗
The eigenvalues are
\begin{equation*} \lambda_1=\frac92, \qquad \lambda_2=\frac12. \end{equation*}
Corresponding unit eigenvectors are
\begin{equation*} \mathbf{v}_1 = \frac1{\sqrt2} \begin{bmatrix} 1\\ 1 \end{bmatrix}, \qquad \mathbf{v}_2 = \frac1{\sqrt2} \begin{bmatrix} 1\\ -1 \end{bmatrix}. \end{equation*}
🔗
The first score vector is
\begin{equation*} \mathbf{t}_1 = Z\mathbf{v}_1 = \frac1{\sqrt2} \begin{bmatrix} 3\\ 3\\ -3\\ -3 \end{bmatrix}. \end{equation*}
🔗
For
\begin{equation*} \mathbf{z}_1 = \begin{bmatrix} 2\\ 1 \end{bmatrix}, \end{equation*}
the score is
\begin{equation*} \mathbf{v}_1^T\mathbf{z}_1 = \frac3{\sqrt2}. \end{equation*}
Thus
\begin{equation*} \widehat{\mathbf{z}}_1 = \frac3{\sqrt2}\mathbf{v}_1 = \begin{bmatrix} 3/2\\ 3/2 \end{bmatrix}, \end{equation*}
and
\begin{equation*} \mathbf{r}_1 = \begin{bmatrix} 1/2\\ -1/2 \end{bmatrix}. \end{equation*}
🔗
We have
\begin{equation*} \mathbf{r}_1\cdot\mathbf{v}_1 = 0. \end{equation*}
Also,
\begin{equation*} \|\mathbf{z}_1\|^2=5, \qquad (\mathbf{v}_1^T\mathbf{z}_1)^2=\frac92, \qquad \|\mathbf{r}_1\|^2=\frac12, \end{equation*}
so
\begin{equation*} 5=\frac92+\frac12. \end{equation*}
🔗
With
\begin{equation*} V = \frac1{\sqrt2} \begin{bmatrix} 1 \amp 1\\ 1 \amp -1 \end{bmatrix}, \end{equation*}
we obtain
\begin{equation*} V^TCV = \begin{bmatrix} 9/2 \amp 0\\ 0 \amp 1/2 \end{bmatrix}. \end{equation*}
🔗
The first direction captures the fraction
\begin{align*} \frac{\lambda_1}{\lambda_1+\lambda_2}\\ \amp=\frac{9/2}{9/2+1/2}\\ \amp=\frac9{10} \end{align*}
of the total centered variation.
🔗
Finally,
\begin{equation*} \bar{\mathbf{x}} + \spans\{\mathbf{v}_1\} = \left\{ \begin{bmatrix} 2\\ 2 \end{bmatrix} + s \begin{bmatrix} 1\\ 1 \end{bmatrix} : s\in\R \right\}. \end{equation*}
This is the line \(y=x\text{.}\)
🔗
🔗
🔗

Definition 6.4.4. Second principal direction.

Suppose \(\mathbf{v}_1\) is a first principal direction. A second principal direction is a unit vector \(\mathbf{v}_2\) that maximizes
\begin{equation*} \mathbf{v}^TC\mathbf{v} \end{equation*}
subject to the two constraints
\begin{equation*} \mathbf{v}^T\mathbf{v}=1 \end{equation*}
and
\begin{equation*} \mathbf{v}^T\mathbf{v}_1=0. \end{equation*}
In \(\R^2\text{,}\) the second constraint leaves only one axis, up to sign. In higher dimensions, it restricts the optimization to the unit vectors orthogonal to \(\mathbf{v}_1\text{.}\)
🔗
🔗

Why is this true?.

On the feasible set, the gradients of the two constraints are
\begin{equation*} 2\mathbf{v} \qquad\text{and}\qquad \mathbf{v}_1. \end{equation*}
They are nonzero and orthogonal, so they are linearly independent by Theorem 4.1.12. Thus Theorem 6.2.10 applies.
🔗
Define
\begin{equation*} L(\mathbf{v},\mu,\nu) = \mathbf{v}^TC\mathbf{v} - \mu(\mathbf{v}^T\mathbf{v}-1) - \nu\mathbf{v}^T\mathbf{v}_1. \end{equation*}
The stationarity equation is
\begin{equation*} 2C\mathbf{v} = 2\mu\mathbf{v}+\nu\mathbf{v}_1. \end{equation*}
🔗
Take the dot product with \(\mathbf{v}_1\text{.}\) Since \(C\) is symmetric,
\begin{align*} \mathbf{v}_1^TC\mathbf{v}\\ \amp=(C\mathbf{v}_1)^T\mathbf{v}\\ \amp=\lambda_1\mathbf{v}_1^T\mathbf{v}\\ \amp=0. \end{align*}
The first constraint term also has zero dot product with \(\mathbf{v}_1\text{.}\) Since
\begin{equation*} \|\mathbf{v}_1\|=1, \end{equation*}
it follows that \(\nu=0\text{.}\) Hence
\begin{equation*} C\mathbf{v}=\mu\mathbf{v}. \end{equation*}
Thus a constrained critical direction is an eigenvector of \(C\text{.}\) Among the eigenvectors orthogonal to \(\mathbf{v}_1\text{,}\) the largest remaining value of the quadratic form is \(\lambda_2\text{.}\)
🔗
🔗
More generally, the \(j\)-th principal direction maximizes
\begin{equation*} \mathbf{v}^TC\mathbf{v} \end{equation*}
subject to unit length and orthogonality to
\begin{equation*} \mathbf{v}_1,\ldots,\mathbf{v}_{j-1}. \end{equation*}
The same argument gives a unit eigenvector for \(\lambda_j\text{.}\) If an eigenvalue is repeated, the individual principal directions inside its eigenspace are not unique, but their span is fixed.
🔗

Principal coordinates.

Collect an orthonormal set of principal directions as the columns of
\begin{equation*} V= \begin{bmatrix} \mathbf{v}_1 \amp \cdots \amp \mathbf{v}_d \end{bmatrix}. \end{equation*}
By Theorem 5.3.11,
\begin{equation*} V^TCV = \begin{bmatrix} \lambda_1 \amp \amp 0\\ \amp \ddots \amp\\ 0 \amp \amp \lambda_d \end{bmatrix}. \end{equation*}
The principal-coordinate matrix is
\begin{equation*} T=ZV. \end{equation*}
Its \(j\)-th column contains the scores in direction \(\mathbf{v}_j\text{,}\) and
\begin{equation*} \frac1nT^TT = V^TCV. \end{equation*}
Thus \(\lambda_j\) is the average squared score in the \(j\)-th principal direction, while the off-diagonal entries are zero.
🔗
The total centered variation is
\begin{equation*} \lambda_1+\cdots+\lambda_d. \end{equation*}
When the centered data are not all zero, the fraction captured by the first \(k\) principal directions is
\begin{equation*} \frac{\lambda_1+\cdots+\lambda_k} {\lambda_1+\cdots+\lambda_d}. \end{equation*}
🔗
🔗

PCA and linear regression.

PCA and linear regression both use projection and sums of squared residuals, but they solve different problems.
🔗
PCA treats the feature coordinates symmetrically. It chooses an affine subspace through the data mean, and its reconstruction residuals are perpendicular to that subspace.
🔗
Linear regression designates one coordinate as the response and minimizes vertical prediction residuals in the data plot. Algebraically, it projects the response vector onto the column space of a design matrix, as in Section 4.3.
🔗
Thus PCA and linear regression can choose different best-fit lines for the same data.
🔗
🔗
For PCA, the principal directions come from
\begin{equation*} C=\frac1nZ^TZ. \end{equation*}
Section 6.5 packages the corresponding input directions, output directions, and stretch factors directly from \(Z\text{,}\) and extends the same picture to an arbitrary rectangular matrix.
🔗
🔗
PrevTopNext