Lecture 7: Eckart-Young, the Closest Rank k Matrix to A

What this lecture covers

Building on the singular value decomposition, Strang states and explains the Eckart-Young theorem: truncating the SVD to its k largest pieces gives the best possible rank-k approximation to a matrix, in several standard senses of "best." Understanding this requires matrix norms, so he introduces three: the spectral (L2) norm, the Frobenius norm, and the nuclear norm, all computable directly from the singular values.

The lecture then applies this to real problems, the Netflix prize and MRI reconstruction as matrix completion problems where the nuclear norm matters, and closes by introducing principal component analysis (PCA) as a fundamentally different fitting problem from ordinary least squares. After watching you should be able to state the Eckart-Young theorem, name the three matrix norms and how they use singular values, and explain how PCA's "perpendicular distance" differs from least squares' "vertical distance."

Key ideas

• Eckart-Young theorem: among all rank-k matrices B, the truncated SVD A_k (built from the k largest singular values and their vectors) minimizes the distance (norm) ||A - B||.
• Vector norms: the L2 norm is ordinary length (sqrt(sum of squares)), the L1 norm is the sum of absolute values, and the L-infinity norm is the largest entry; minimizing in the L1 norm tends to produce sparse (mostly-zero) solutions, unlike L2.
• Matrix norms built from singular values: the L2 (spectral) norm is the largest singular value σ1; the Frobenius norm is the square root of the sum of squares of all entries; the nuclear norm is the sum of all the singular values.
• Orthogonal invariance: multiplying a matrix by an orthogonal matrix on either side does not change its singular values or its norms, since QU is still orthogonal whenever Q and U are.
• Netflix and MRI as matrix completion: recovering missing entries in a large data matrix (movie ratings, MRI scans) by minimizing the nuclear norm is the key idea behind both the Netflix Prize approach and undersampled MRI reconstruction.
• PCA versus least squares: least squares minimizes the sum of squared vertical errors between data points and a fitted line; PCA instead minimizes the sum of squared perpendicular distances from the points to a line through the (mean-centered) data, a different problem with a different answer.
• PCA's answer comes from the SVD: after centering the data (subtracting the mean) and forming the sample covariance matrix AA^T, the best-fit direction for PCA is given by the leading singular vector, connected to the largest singular value σ1.

Walkthrough

The Eckart-Young theorem (1:03)

Strang states the central theorem of the lecture: for any matrix B of rank k, the distance from A to B is at least as large as the distance from A to A_k, the matrix built from the k largest pieces of the SVD. This means the SVD, truncated to its most significant terms, gives the best possible low-rank summary of a matrix, a result credited to Eckart and Young.

Vector and matrix norms (4:04)

Strang reviews the L2, L1, and L-infinity norms for vectors, noting that minimizing in the L1 norm tends to produce sparse solutions with mostly zero components, a property with major applications in signal processing. He then defines three matrix norms that all depend only on the singular values: the L2 (spectral) norm is the largest singular value, the Frobenius norm treats the matrix as one long vector and takes its L2 norm, and the nuclear norm sums all the singular values.

Netflix and MRI as matrix completion problems (15:12)

Strang explains that the nuclear norm turned out to be the right quantity to minimize in the Netflix Prize competition, where a large matrix of movie ratings has many missing entries that must be filled in to predict a viewer's unseen preferences. The same idea, completing a matrix with missing data by minimizing its nuclear norm, applies to reconstructing MRI images from undersampled scans.

Why orthogonal multiplication preserves norms (27:22)

Using a diagonal example with singular values 4, 3, 2, 1, Strang shows that the best rank-two approximation keeps the two largest singular values, and that any attempt to spread error differently across the matrix (even improving the diagonal) makes the total error worse once off-diagonal entries are introduced. He then shows that multiplying a matrix by an orthogonal matrix Q on the left leaves its singular values and all three norms unchanged, since QU remains orthogonal, which is why the Eckart-Young theorem is not just a special property of diagonal matrices.

PCA versus least squares (31:24)

Strang sets up a small example, data on height and age, and shows the first step is centering the data by subtracting the mean of each row so the data cloud is centered at the origin. He contrasts this with ordinary least squares, which minimizes the sum of squared vertical distances from data points to a fitted line (solved via the normal equations A^T A x̂ = A^T b) and explains that PCA instead minimizes the sum of squared perpendicular distances, a different problem that uses the sample covariance matrix AA^T and whose best-fit direction is given by the leading singular vector of the data matrix.

Before you watch

• Watch Lecture 6 on the singular value decomposition first, since this lecture builds the Eckart-Young theorem and PCA directly on top of A = UΣV^T.
• Familiarity with least squares and the normal equations A^T A x̂ = A^T b helps when comparing PCA to least squares.

Check your understanding

1. What does the Eckart-Young theorem say about the truncated SVD A_k?
2. How are the L2 (spectral), Frobenius, and nuclear norms of a matrix each computed from its singular values?
3. Why does multiplying a matrix by an orthogonal matrix leave its norms and singular values unchanged?
4. How does the nuclear norm relate to the Netflix Prize and MRI reconstruction problems?
5. What is the key difference between what least squares minimizes and what PCA minimizes when fitting a line to data?