Lecture 34: Distance Matrices, the Procrustes Problem

What this lecture covers

This short lecture first resolves a loose end from the previous distance-matrix discussion: what goes wrong when three given distances violate the triangle inequality. It then introduces the Procrustes problem, finding the best orthogonal transformation that maps one set of vectors as closely as possible onto another, using the Frobenius norm and the singular value decomposition.

After watching, you can explain why a distance matrix that violates the triangle inequality produces a Gram matrix that fails to be positive semi-definite, and you can state and use the formula for the best orthogonal matrix solving the Procrustes problem.

Key ideas

• Triangle inequality as a feasibility test: if three given pairwise distances violate the triangle inequality, no set of points in any dimension can have exactly those distances.
• Link to the Gram matrix: the distance matrix D determines a dot product (Gram) matrix G = X^T X; when the triangle inequality fails, the resulting G is not positive semi-definite (it has a negative eigenvalue), which is exactly why no valid X exists.
• Procrustes problem: given two sets of vectors X and Y (for example, two coordinate computations of the same satellite positions), find the orthogonal matrix Q that makes YQ as close as possible to X, minimizing the Frobenius norm of the difference.
• Frobenius norm: the norm of a matrix treated as one long vector of entries; it can equivalently be computed as the trace of A^T A (or A A^T), or as the sum of squared singular values.
• Orthogonal matrices preserve the Frobenius norm: multiplying a matrix by an orthogonal matrix Q does not change its singular values or its Frobenius norm, which is central to solving the Procrustes problem.
• Trace identities: trace(A^T B) = trace(B^T A) = trace(B A^T), and more generally trace(CD) = trace(DC), because CD and DC share the same nonzero eigenvalues.
• Solution via SVD: the best orthogonal matrix is Q = U V^T, where U Sigma V^T is the singular value decomposition of Y^T X.

Walkthrough

Revisiting the triangle inequality failure (0:01)

The lecture returns to a distance matrix example from the previous session where three prescribed distances violate the triangle inequality (a squared distance of 6 where the triangle inequality allows at most 4). It shows that increasing the dimension does not help, since the triangle inequality holds regardless of dimension, and traces the failure back to the Gram matrix G derived from D failing to be positive semi-definite: distances satisfy the triangle inequality if and only if the corresponding G is positive semi-definite, in which case valid points can always be found.

Introducing the Procrustes problem (10:10)

Named after the Greek myth of a host who forced visitors to fit his bed rather than adjusting the bed, the Procrustes problem asks for the orthogonal matrix Q that best maps one set of vectors Y onto another set X, minimizing |YQ - X| in the Frobenius norm. The lecture reviews three equivalent formulas for the Frobenius norm (sum of squared entries, trace of A^T A, and sum of squared singular values) and shows that multiplying by an orthogonal matrix does not change a matrix's singular values or its Frobenius norm.

Observations about traces (21:00)

To manipulate the minimization problem, the lecture establishes trace identities: trace(A^T B) = trace(B^T A) = trace(B A^T), justified by noting that transposing a matrix does not change its diagonal (and hence its trace).

Reverse the order of two matrices (22:52)

The lecture proves that trace(CD) = trace(DC) by noting that CD and DC share the same nonzero eigenvalues, even when the matrices have different shapes, so any extra zero eigenvalues from shape mismatches do not affect the trace. This identity is the key tool for simplifying the Procrustes minimization.

The solution: Q = UV^T (26:03)

Using the trace identities and the singular value decomposition of Y^T X = U * Sigma * V^T, the lecture states the result: the best orthogonal matrix solving the Procrustes problem is Q = U V^T. The lecture closes by flagging an open question for the next class about whether deep learning reliably works in practice, based on a conversation with a colleague.

Before you watch

• Watch the previous lecture on distance matrices, which introduces the Gram matrix G = X^T X and its relationship to a distance matrix D.
• Review the singular value decomposition and the definition of a positive semi-definite matrix.
• Be comfortable with the trace of a matrix and basic properties of orthogonal matrices.

Check your understanding

1. Why does violating the triangle inequality among three given distances make it impossible to find matching points in any dimension?
2. How does a distance matrix's failure of the triangle inequality show up as a property of the corresponding Gram matrix?
3. What three equivalent ways can the Frobenius norm of a matrix be computed?
4. Why does multiplying a matrix by an orthogonal matrix leave its Frobenius norm unchanged?
5. What is the formula for the orthogonal matrix that best solves the Procrustes problem, and what pieces of the SVD does it use?