Lecture 16: Derivatives of Inverse and Singular Values

What this lecture covers

The lecture answers a question left open from the previous class: if a matrix A(t) changes over time, how does its largest singular value change? Strang first revisits a simpler warm-up, the derivative of A squared, to show why matrix derivatives don't behave like scalar derivatives when matrices don't commute. He then builds the parallel formula for the derivative of a singular value using the SVD and a three-term product rule.

The second half shifts to a different question: instead of exact derivatives, how much can eigenvalues and singular values move under a finite change to a matrix? This leads to Weyl's inequality and the interlacing of eigenvalues. The lecture closes by connecting these ideas to compressed sensing, the nuclear norm, and matrix completion, the math behind problems like filling in missing entries in a ratings matrix. After watching, you should be able to derive the singular value derivative formula yourself and explain why the nuclear norm plays the same role for matrices that the l1 norm plays for sparse vectors.

Key ideas

• Derivative of A squared: is not 2A dA/dt, because matrices don't commute; the correct formula is A dA/dt + dA/dt A.
• Derivative of a singular value: dSigma/dt = u^T (dA/dt) v, where u and v are the left and right singular vectors of A at that instant, exactly parallel to the eigenvalue derivative formula dLambda/dt = x^T (dA/dt) x.
• Product rule proof: differentiating Sigma = u^T A v gives three terms; the two unwanted terms vanish because u^T u = 1 and v^T v = 1 have zero derivative.
• Weyl's inequality: for symmetric matrices S and T, the eigenvalues of S + T are bounded above by sums of eigenvalues of S and T, which is the source of eigenvalue interlacing.
• Interlacing of eigenvalues: adding a positive rank-one change to a symmetric matrix pushes eigenvalues up or leaves them unchanged, but a lower eigenvalue can never jump past the next higher original eigenvalue.
• Nuclear norm: the sum of a matrix's singular values, the matrix analogue of the vector l1 norm.
• Matrix completion: filling in unknown entries (like missing movie ratings) by choosing the completion that minimizes the nuclear norm, which favors low-rank solutions.
• Zero norm: not a true norm (it doesn't scale properly), but informally counts nonzero entries for a vector or, for a matrix, corresponds to the rank.

Walkthrough

Derivative of a matrix squared (0:00)

Strang opens by revisiting the derivative of A squared using the limit definition: expand (A + deltaA)^2 - A^2, divide by deltaT, and let deltaT go to zero. Because A and deltaA don't generally commute, the cross terms A deltaA and deltaA A are different, so the result is A dA/dt + dA/dt A, not 2A dA/dt. This sets up the point that order matters throughout the lecture's matrix calculus.

Derivative of a singular value (7:07)

Building on last lecture's formula for the derivative of an eigenvalue, dLambda/dt = x^T (dA/dt) x, Strang derives the parallel result for singular values: dSigma/dt = u^T (dA/dt) v. The proof starts from Sigma = u^T A v and uses the SVD relations Av = Sigma u and A^T u = Sigma v to rewrite the formula two ways, both giving Sigma. Taking the derivative of Sigma = u^T A v produces three terms by the product rule: (du/dt)^T A v, u^T (dA/dt) v, and u^T A (dv/dt). Substituting the SVD relations into the first and third terms turns them into expressions like Sigma (du/dt)^T u, which vanish because u^T u = 1 has zero derivative (and similarly for v). Only the middle term survives, giving the clean result.

Interlacing of eigenvalues (17:24)

The lecture moves from exact derivatives to bounds on finite changes. For a symmetric matrix S with eigenvalues lambda_1 >= lambda_2 >= ..., changing S by adding a positive rank-one matrix produces new eigenvalues mu_1 >= mu_2 >= ... that satisfy interlacing: each mu_i is at least lambda_i, but mu_2 can never exceed lambda_1. Strang works through a puzzle he had emailed the class: if you keep boosting the second eigenvalue by a growing amount theta, it looks like it should eventually pass the first eigenvalue and break the bound. The resolution is that once the boosted value reaches lambda_1, it simply becomes the new top eigenvalue rather than passing it, so the ordering never actually fails.

This leads to Weyl's inequality, the general statement that for symmetric matrices S and T, an eigenvalue of S + T is bounded by a sum of an eigenvalue of S and an eigenvalue of T, with the index rule lambda_{i+j-1}(S+T) <= lambda_i(S) + lambda_j(T). Choosing j = 1 recovers the simple bound that eigenvalues can rise by at most the largest eigenvalue of the change. Strang notes the notes contain two proofs of interlacing, the standard Weyl approach and a graph-based argument, and mentions that the same interlacing behavior holds for singular values of any matrix, not just eigenvalues of symmetric ones.

Compressed sensing, the nuclear norm, and matrix completion (34:30)

Strang introduces the nuclear norm of a matrix as the sum of its singular values, the natural matrix counterpart to the vector l1 norm. He recalls that minimizing the l1 norm subject to a linear constraint tends to produce sparse solutions, and the zero norm of a vector, informally the count of nonzero entries, is not a true norm because it doesn't scale correctly when you multiply a vector by a constant. The nearest true norm to it is the l1 norm.

For matrices, the equivalent of the zero norm is the rank, which is also not a true norm, and the nearest true norm is the nuclear norm. This connects directly to matrix completion: given a matrix with many missing entries, such as a table of movie ratings where most entries are unknown, a good way to fill them in is to choose the completion that minimizes the nuclear norm, favoring low-rank structure. Strang mentions this is the underlying idea behind the kind of problem Netflix made famous, and notes that whether gradient descent in deep learning tends to find nuclear-norm-minimizing solutions is a conjecture, proven only in some related cases, not in general.

Before you watch

• Review the derivative of an eigenvalue formula, dLambda/dt = x^T (dA/dt) x, from the previous lecture, since this lecture builds the singular value version in parallel.
• Be comfortable with the SVD relations Av = Sigma u and A^T u = Sigma v.
• Recall the l1 norm and why minimizing it tends to produce sparse vector solutions; this motivates the nuclear norm discussion at the end.

Check your understanding

1. Why is the derivative of A squared equal to A dA/dt + dA/dt A rather than 2A dA/dt?
2. Starting from Sigma = u^T A v, explain why two of the three product-rule terms vanish when computing dSigma/dt.
3. In the interlacing puzzle, why doesn't a rank-one boost to the second eigenvalue ever actually overtake the first eigenvalue?
4. What does Weyl's inequality say about the eigenvalues of S + T in terms of the eigenvalues of S and T separately?
5. Why is the nuclear norm a natural choice for matrix completion problems like filling in missing ratings?