high-dim
The matrix with 99% holes
It is 2007, and a DVD-rental company has posted a million-dollar bounty on its recommendation engine, releasing a ratings matrix of half a million users by twenty thousand films — with 99 percent of the entries missing, since nobody rates more than a sliver. Filling in the blanks looks hopeless until structure enters: tastes are approximately low-rank, a few latent factors explaining most preference. Establish when completion is genuinely possible — which sampling patterns and incoherence conditions permit exact recovery of a low-rank matrix from a vanishing fraction of entries via convex relaxation — and when the same matrix is unrecoverable. Get it wrong and recommenders hallucinate preferences for the sparsely observed, and the same mathematics misfires later in imaging and genomics, where the filled-in entries drive diagnoses.
Who this problem belongs to
The two figures whose methods fit it best, out of 62 in contention.
This is Candes's own founding result, not an analogy. With Benjamin Recht, his 2009 paper 'Exact Matrix Completion via Convex Optimization' established precisely the theory this problem describes: when a low-rank matrix can be exactly recovered from a small, incoherent random sample of its entries by solving a convex nuclear-norm minimization, and under what incoherence conditions between the matrix's row and column spaces and the sampling pattern this is possible. Developed within two years of the actual Netflix Prize competition, his work directly answers when completion is genuinely possible and when it is not, exactly the honest boundary this problem demands. Dropped into 2007, he is not applying a general toolkit to this problem; he built the specific mathematics that answers it almost immediately afterward.
Srebro's doctoral and postdoctoral work centered specifically on matrix factorization for collaborative filtering, including max-margin matrix factorization, developed in the mid-2000s directly for exactly this kind of sparse ratings-matrix problem. He formalized the low-rank assumption underlying recommender systems, connected it to generalization theory via matrix norms, and reasoned rigorously about which sampling patterns permit reliable factorization. That gives him firsthand, contemporaneous engagement with the Netflix Prize problem's actual technical substance, arguably closer to the applied recommender-systems setting than Candes's more general compressed-sensing formulation. His score sits just below Candes because the specific convex-relaxation exact-recovery guarantees under incoherence were formalized slightly more rigorously and generally in the Candes-Recht line of work.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
62 figures are scored on this problem. Draw it in a battle to see where you land.