Candès-Recht 2009: random n×n rank-r matrix can be recovered from O(rn log n) entries with high probability. Nuclear norm = convex surrogate for rank.
Left: true matrix. Center: observed (white=missing). Right: completed. Color = value.
Singular value spectrum: true (orange), observed mask (gray), completed (blue).