nuclear (trace) norm

The nuclear norm is the simplest possible summary of a matrix's singular values: just add them all up. ||A||_* = sigma_1 + sigma_2 + ... + sigma_r. Where the spectral norm takes the max and the Frobenius norm takes the root-sum-of-squares, the nuclear norm takes the plain sum. These three are the Schatten infinity-, 2-, and 1-norms — the same lp idea applied to the vector of singular values.

Its star role is as a convex surrogate for rank. Minimizing rank directly is combinatorial and NP-hard; rank counts how many singular values are nonzero, which is a discontinuous, non-convex thing. The nuclear norm is the tightest convex function that approximates rank (its convex envelope on the spectral-norm unit ball), much as the l1 norm is the convex surrogate for counting nonzero entries in a vector.

This is what powers matrix completion. Given a matrix with most entries missing (think a ratings table you want to fill in), you look for the matrix that matches the observed entries and has the smallest nuclear norm. Because minimizing nuclear norm pushes toward low rank, you recover a structured, low-rank completion — and remarkably, under mild conditions, you recover the true matrix exactly. This is the engine behind the Netflix-style recommendation breakthroughs.

The practical appeal is that nuclear-norm minimization is a convex optimization problem, so it has a global optimum reachable by reliable solvers, unlike the intractable direct rank minimization. You pay a small price in exactness for an enormous gain in tractability.