Principal Component Analysis

PCA is a linear dimensionality reduction method. It replaces your original coordinate system (your original features) with a new coordinate system whose axes are:

• •Orthogonal (perpendicular) directions in feature space
• •Ordered by how much variance of the data they capture when you project onto them

Those axes are called principal components.

The geometric picture

Imagine your data points as a cloud in ℝᵈ (d features). If that cloud is stretched out more in one direction than others, there’s a “long axis” through the cloud. Projecting onto that axis preserves a lot of the spread (variance) of the data. PCA finds that axis, then the next-most-informative orthogonal axis, and so on.

Conventions (define them early)

We’ll set up notation carefully so you don’t have to guess later.

• •Data matrix: $X \in \mathbb{R}^{n \times d}$ with rows $\mathbf{x}_i^T$ (each $\mathbf{x}_i \in \mathbb{R}^d$ is one sample).
• •Sample mean:

• •Centered data matrix:

where $\mathbf{1} \in \mathbb{R}^{n}$ is the all-ones column vector.

• •Covariance matrix. Two common conventions:
• •Population-style: $\Sigma = \frac{1}{n} X_c^T X_c$
• •Unbiased sample-style: $\Sigma = \frac{1}{n-1} X_c^T X_c$

For PCA, the eigenvectors are the same under both (they differ only by a scalar factor in eigenvalues). In this lesson, we’ll mostly use

to keep algebra clean.

What PCA outputs

PCA produces:

• •Principal component directions: v₁, …, vᵈ (unit vectors in ℝᵈ), collected in a matrix $V = [\mathbf{v}_1\ \cdots\ \mathbf{v}_d]$.
• •Corresponding eigenvalues: $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_d \ge 0$.

Interpretation:

• •vⱼ is a direction (axis) in feature space.
• •$\lambda_j$ is the variance of the data when projected onto vⱼ.

Two equivalent “best” statements

When you keep only the top-k components, PCA gives the best k-dimensional linear approximation in two equivalent ways:

1) Maximum captured variance among all k-dimensional subspaces.

2) Minimum squared reconstruction error among all rank-k linear projections.

We’ll prove both—but slowly, with checkpoints.

Checkpoint summary

• •PCA is a change of basis to orthogonal directions ordered by variance.
• •Compute PCA from the covariance eigenvectors (or from SVD).
• •Keeping top-k components gives an optimal k-dimensional linear representation.

Micro-exercise (30 seconds)

If you scale your covariance by 1/(n−1) instead of 1/n, what changes?

Answer: eigenvectors (principal directions) do not change; eigenvalues scale by $\frac{n}{n-1}$.

PCA starts with a very specific optimization question:

Among all unit directions v in feature space, which direction makes the projected data have the largest variance?

That direction will be v₁, the first principal component.

Step 1: Define projection and projected variance

Take a unit vector v ∈ ℝᵈ with $\|\mathbf{v}\|_2 = 1$.

Project a centered data point $\mathbf{x}$ onto v:

• •Scalar coordinate along v: $z = \mathbf{v}^T \mathbf{x}$.

For a random centered vector x (think of drawing a row from $X_c$), the variance of $z$ is:

Using $\mathrm{Cov}(\mathbf{x}) = \Sigma$ and standard covariance rules:

So we want to maximize $\mathbf{v}^T \Sigma \mathbf{v}$ subject to $\|\mathbf{v}\|_2 = 1$.

Step 2: The optimization problem

The expression

is the Rayleigh quotient. Under the unit-norm constraint, maximizing $\mathbf{v}^T\Sigma\mathbf{v}$ is the same as maximizing $R(\mathbf{v})$.

Step 3: Solve with Lagrange multipliers (show work)

Set up the Lagrangian:

Differentiate w.r.t. v and set to zero:

1) Gradient of quadratic form: $\nabla_{\mathbf{v}} (\mathbf{v}^T \Sigma \mathbf{v}) = 2\Sigma\mathbf{v}$ (since $\Sigma$ is symmetric)

2) Gradient of constraint term: $\nabla_{\mathbf{v}} (\mathbf{v}^T\mathbf{v}) = 2\mathbf{v}$

So:

Divide by 2:

That is exactly the eigenvector equation.

So any optimum must be an eigenvector of $\Sigma$.

To see which eigenvector gives the maximum, plug an eigenvector v with eigenvalue $\lambda$ into the objective:

Under the unit constraint, the value equals its eigenvalue. Therefore, the maximum is attained by the eigenvector with the largest eigenvalue.

So:

• •v₁ = eigenvector of $\Sigma$ with largest eigenvalue $\lambda_1$
• •Captured variance along v₁ is $\lambda_1$

Step 4: The next components (orthogonality emerges)

After choosing v₁, we want v₂ to maximize variance subject to being orthogonal to v₁:

The solution is the eigenvector with the next-largest eigenvalue, and so on. Because $\Sigma$ is symmetric positive semidefinite, it has an orthonormal eigenbasis, so the eigenvectors can be chosen orthogonal.

Checkpoint summary

• •Projected variance along v is $\mathbf{v}^T\Sigma\mathbf{v}$.
• •Maximizing this under $\|\mathbf{v}\|=1$ gives an eigenvector problem.
• •The best direction is the eigenvector with largest eigenvalue.

Micro-exercise (1 minute)

Let $\Sigma = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}$. Which unit vector maximizes $\mathbf{v}^T\Sigma\mathbf{v}$?

Solution sketch: eigenvalues are 2 and 1 with eigenvectors [1,0]ᵀ and [0,1]ᵀ. Max is along [1,0]ᵀ with value 2.

Finding v₁ is only the beginning. PCA’s power comes from selecting a whole k-dimensional subspace that best represents the data.

There are two common ways to describe what “best” means:

1) Keep as much variance as possible (information-as-spread viewpoint)

2) Reconstruct with minimal squared error (compression viewpoint)

A key learning goal is to see why these are actually the same objective.

Part A: Projecting onto the top-k components

Let $V_k = [\mathbf{v}_1\ \cdots\ \mathbf{v}_k] \in \mathbb{R}^{d \times k}$ with orthonormal columns ($V_k^T V_k = I_k$).

Given a centered data point x, its coordinates in the PCA subspace are:

The projection back to ℝᵈ (the rank-k approximation of x) is:

So the projection matrix is $P_k = V_k V_k^T$.

Part B: Captured variance in k dimensions

The variance captured by projecting onto the k-dimensional subspace is the expected squared norm of the projected vector:

Compute it:

\[\begin{aligned}

\mathbb{E}[\|V_k^T \mathbf{x}\|_2^2]

&= \mathbb{E}[ (V_k^T \mathbf{x})^T (V_k^T \mathbf{x}) ] \\

&= \mathbb{E}[ \mathbf{x}^T V_k V_k^T \mathbf{x} ] \\

&= \mathrm{tr}(\mathbb{E}[ \mathbf{x}\mathbf{x}^T ] V_k V_k^T) \quad \text{(cyclic trace)} \\

&= \mathrm{tr}(\Sigma V_k V_k^T).

\end{aligned}\]

If $V_k$ is made of eigenvectors of $\Sigma$, then:

So the top-k PCA subspace captures variance equal to the sum of the top k eigenvalues.

Explained variance ratio

A common diagnostic is:

This tells you what fraction of total variance you keep.

Checkpoint summary

• •The rank-k projection is $\hat{\mathbf{x}} = V_k V_k^T \mathbf{x}$.
• •Variance captured by that subspace is $\sum_{j=1}^k \lambda_j$.
• •Explained variance ratio guides k selection.

Micro-exercise (45 seconds)

If eigenvalues are [5, 2, 1, 1, 1], what k gives ≥80% explained variance?

Solution: total = 10. k=1 gives 50%, k=2 gives 70%, k=3 gives 80% → k=3.

Part C: Reconstruction error and why PCA is optimal

Now we switch viewpoints: you want to compress data by keeping only k numbers per sample (the coordinates z) and then reconstruct.

For a point x, reconstruction error is:

Consider expected reconstruction error over the data distribution:

Key identity: energy splits into kept + lost

Because $V_k V_k^T$ is an orthogonal projector,

• •the kept component is $\hat{\mathbf{x}}$
• •the residual is $\mathbf{r} = \mathbf{x} - \hat{\mathbf{x}}$
• •and $\hat{\mathbf{x}} \perp \mathbf{r}$

So by Pythagoras:

Rearrange:

Take expectation:

\[\begin{aligned}

\mathbb{E}[\|\mathbf{x} - V_k V_k^T \mathbf{x}\|_2^2]

&= \mathbb{E}[\|\mathbf{x}\|_2^2] - \mathbb{E}[\|V_k V_k^T \mathbf{x}\|_2^2] \\

&= \mathbb{E}[\|\mathbf{x}\|_2^2] - \mathbb{E}[\|V_k^T \mathbf{x}\|_2^2].

\end{aligned}\]

The first term $\mathbb{E}[\|\mathbf{x}\|_2^2]$ is constant with respect to the choice of subspace. So:

Minimizing reconstruction error is equivalent to maximizing captured projected energy/variance.

So the same $V_k$ that maximizes $\mathbb{E}[\|V_k^T \mathbf{x}\|^2]$ also minimizes reconstruction error.

What is the minimum error value?

If you choose $V_k$ as top-k eigenvectors, the variance you don’t capture is the sum of remaining eigenvalues:

This gives a clean interpretation:

• •Eigenvalues are “energy per principal axis.”
• •Dropping axes j>k loses exactly that energy.

Checkpoint summary

• •Reconstruction error = total energy − captured energy.
• •PCA maximizes captured energy, therefore minimizes reconstruction error.
• •Minimum achievable expected squared error after keeping k comps is $\sum_{j>k} \lambda_j$.

Micro-exercise (1 minute)

Eigenvalues are [10, 3, 2]. If you keep k=1, what is expected reconstruction error (in variance units)?

Solution: drop eigenvalues 3 and 2 → error = 5.

Part D: Best rank-k approximation (matrix view)

So far we reasoned per-vector. PCA also gives the best rank-k matrix approximation of the centered data matrix $X_c$ in Frobenius norm.

Let $X_c$ have SVD:

(where we’ll call the diagonal of singular values $\Sigma_s$ to avoid confusing it with covariance).

The Eckart–Young theorem says the best rank-k approximation is:

This is exactly what PCA is doing in matrix form.

Connecting to covariance:

\[\begin{aligned}

\frac{1}{n} X_c^T X_c

&= \frac{1}{n} (V \Sigma_s U^T)(U \Sigma_s V^T) \\

&= \frac{1}{n} V \Sigma_s^2 V^T.

\end{aligned}\]

So:

• •The PCA eigenvectors are the right singular vectors $V$.
• •The PCA eigenvalues are $\lambda_j = \frac{\sigma_j^2}{n}$ where $\sigma_j$ is singular value j.

That’s why PCA can be computed without explicitly forming the covariance matrix, especially when d is large.

Checkpoint summary

• •PCA is equivalent to truncated SVD of centered data.
• •Eigenvalues relate to singular values via $\lambda_j = \sigma_j^2/n$.
• •Best rank-k approximation in Frobenius norm matches the best k-dimensional subspace story.

PCA is simple to state but easy to misuse in practice. This section focuses on how PCA is applied, what choices matter, and how it connects to the tools you already know.

A practical PCA workflow

Step 0: Decide the goal

Common goals:

• •Visualization (k=2 or 3)
• •Compression / speed-up downstream models
• •Denoising
• •Preprocessing for regression/classification (sometimes helps, sometimes hurts)

Step 1: Preprocess (centering is non-negotiable)

PCA assumes the data is centered.

• •Compute mean $\boldsymbol{\mu}$ over training set.
• •Subtract it from all training points.

If you forget this, the first component can point mostly toward the mean rather than describing variation.

Step 2: Scaling / standardization (depends on units)

If features have different units/scales, covariance will be dominated by high-variance features.

Standardization: $x_{ij} \leftarrow (x_{ij} - \mu_j)/s_j$ where $s_j$ is std dev.

Step 3: Compute PCA (covariance eigendecomp or SVD)

Two equivalent computation paths:

Path A: Covariance eigen-decomposition (good when d is modest):

1. 1)$\Sigma = \frac{1}{n} X_c^T X_c$
2. 2)Eigen-decompose: $\Sigma = V\Lambda V^T$

Path B: SVD of centered data (often better numerically and when d is large):

1. 1)$X_c = U\Sigma_s V^T$
2. 2)Columns of $V$ are principal directions, and eigenvalues are $\lambda_j = \sigma_j^2/n$.

Step 4: Choose k

Typical heuristics:

• •Keep enough components for 90–99% explained variance
• •Scree plot “elbow”
• •Cross-validate downstream task performance

Step 5: Transform and (optionally) reconstruct

Transform (encode):

Reconstruct (decode):

(remember to add the mean back).

Checkpoint summary

• •Always center using training mean.
• •Consider standardization if feature scales differ.
• •Use SVD when d is large or for stability.

Micro-exercise (1 minute)

Why must you apply the training mean and scaling to the test set (not recompute them on test)?

Solution: recomputing uses test information (data leakage) and changes the coordinate system; transformed features wouldn’t be comparable.

PCA as “rotation + truncation”

When $V$ is orthonormal, multiplying by $V$ is a rotation/reflection (distance-preserving). PCA can be thought of as:

1) Rotate into the eigenvector basis: $\mathbf{y} = V^T \mathbf{x}$

2) Drop the last d−k coordinates (small-variance directions)

This makes clear why PCA often denoises: if noise is roughly isotropic, it spreads across many directions and tends to be captured by small eigenvalues.

Whitening (optional but common)

Sometimes you want the transformed variables to have unit variance and be uncorrelated. PCA already makes them uncorrelated; whitening also rescales.

Let $\Lambda_k$ be diagonal with top-k eigenvalues. PCA coordinates are:

Whitened coordinates:

Caution: whitening can amplify noise in low-variance directions (because you divide by small $\lambda$).

Connections to SVD (tying back to prerequisite)

Since you already know SVD, here’s the clean link you can reuse:

• •Compute SVD: $X_c = U\Sigma_s V^T$
• •Principal components are columns of $V$
• •Scores (projected coordinates) are $Z = X_c V_k = U_k\Sigma_{s,k}$

This last identity is handy: you can get the k-dimensional representation directly as $U_k\Sigma_{s,k}$ without forming $V_k$ explicitly in some streaming/large-scale settings.

When PCA is not the right tool

PCA is linear. It fails when structure is nonlinear.

• •A “Swiss roll” manifold in 3D is not well represented by a plane.
• •Clusters separated nonlinearly might need kernel PCA, t-SNE/UMAP for visualization, or autoencoders for nonlinear compression.

Still, PCA is often the baseline: fast, interpretable, and a strong first step.

Final checkpoint summary

• •PCA is optimal among linear k-dimensional subspaces.
• •Implementation requires centering, and often scaling.
• •SVD is typically the computational workhorse.
• •PCA is a baseline; nonlinear methods are for nonlinear structure.