I.9Principal Components and the Best Low Rank Matrix

The one idea

I.8 gave you A = σ₁u₁v₁ᵀ + σ₂u₂v₂ᵀ + ⋯, ordered by importance. The obvious move is to keep the first k terms and throw away the rest, giving Aₖ.

The Eckart-Young theorem says that obvious move is optimal:

Of all matrices of rank k, none is closer to A than Aₖ.

Not “a reasonable heuristic.” The best, and it stays the best in the spectral norm, the Frobenius norm, and every other norm invariant under orthogonal transformation. You are not choosing a compression scheme and hoping; the answer is settled.

The error you accept is exactly the part you discarded, in the Frobenius norm, ‖A − Aₖ‖²_F = σ²_{k+1} + ⋯ + σ²_r. The singular values you drop are your error budget, and you can read it off before you commit.

PCA is this, plus centring

Principal Component Analysis is Eckart-Young applied to data:

1. Put your samples in a matrix, one column per sample.
2. Subtract the row means. This step is the whole difference between PCA and a bare SVD, and skipping it is the classic mistake.
3. Take the SVD of the centred matrix.
4. The columns of U are the principal directions. σᵢ²/(n−1) is the variance captured along direction i.

The first principal component is the direction of greatest variance in your data. The second is the best remaining direction perpendicular to the first, and so on. Because U is orthogonal, the components never repeat information.

Note the connection back to V.4: the sample covariance matrix is essentially AAᵀ/(n−1) for centred A, so PCA is an eigen-decomposition of the covariance matrix, computed via the SVD, which is more numerically stable than forming the covariance matrix explicitly.

Why it matters later

• III.3 asks when singular values decay fast. Fast decay is precisely when a small k suffices, so that section tells you when this one is practical.
• III.5 (compressed sensing, matrix completion) recovers a matrix from partial data by assuming it is low rank. Netflix-style recommendation is this idea.
• IV.7 clustering and VII dimension reduction before a network both lean on the same truncation.

What to actually do

1. Generate 200 points in 2-D along a tilted line with a little noise. Centre them, take the SVD, and plot the two principal directions on the scatter. The first should lie along the line, see it, do not just compute it.
2. Compute σ₁²/(σ₁² + σ₂²). That is the fraction of variance the first component explains.
3. Repeat without centring the data and watch the first component swing toward the origin-to-mean direction instead. This is the failure mode worth experiencing once.
4. On a real dataset (sklearn’s digits works well), plot σᵢ against i. Find the knee. That knee is your k.

Check yourself

• What is ‖A − Aₖ‖ in the spectral norm? (One symbol.)
• Why can’t a rank-k matrix ever beat Aₖ?
• What breaks if you skip centring?
• Your singular values are all roughly equal. What does that tell you about reducing dimension on this data?

Common sticking points

Assuming the top component is the useful one. Eckart-Young optimises for variance, not for whatever you care about. A high-variance direction can be pure measurement noise, and a low-variance direction can carry the signal that matters for classification. PCA is unsupervised, it has never seen your labels.

Forgetting to scale. If one feature is in metres and another in millimetres, the millimetre feature dominates the variance for no real reason. Standardise features to comparable units before PCA unless you have a specific reason not to.

Reading too much into the components. Principal directions are mathematically determined, not physically meaningful. A component is a weighted mix of your original features; it need not correspond to anything nameable.