Matrix Completion
Lay every user out as a row and every item as a column, then put a rating in the cell where the two meet. Almost every cell is empty — on a real catalogue, well over 99% of them. Matrix completion is the problem of filling the blanks in.
Why it is possible at all
Filling in arbitrary blanks is hopeless; filling in these ones is not, because taste is structured. If preferences are driven by a modest number of underlying factors — genre, era, pace, polish — the full matrix is approximately low-rank, and a low-rank matrix has far fewer free parameters than it has cells. That is the result the field rests on: under the right conditions such a matrix can be recovered from a small random sample of its entries, by finding the lowest-nuclear-norm matrix consistent with what was observed.
How it is actually done
Nuclear-norm minimisation is elegant but heavy, so production systems solve a regularised version directly: factor the matrix into user and item factors and fit them to the observed cells by squared error with an L2 penalty. Funk SVD does this with gradient descent, ALS with alternating closed-form solves. The prediction for an empty cell is then the dot product of the two factor vectors.
Where the framing breaks
Completion theory assumes entries are missing at random. Ratings are not: people rate what they chose to watch, and watch what they were shown. The error that matters is also not reconstruction error across the whole grid but the quality of the top handful of items, which is why most modern systems abandon completion for ranking objectives learned from implicit feedback.
Matrix completion frames recommendation as filling in the unobserved cells of a sparse user-item matrix, on the assumption that the complete matrix is approximately low-rank. In practice it is solved by fitting user and item factors to the observed entries with regularised squared error, which is what underpins rating prediction and classical matrix factorisation. Its weak point is the assumption that entries are missing at random — they are not.
Think of an enormous spreadsheet. Every row is a person, every column is a film, and a cell holds what that person thought of that film. Almost the whole sheet is blank, because nobody watches more than a tiny slice of what exists.
Matrix completion is the job of sensibly guessing the blanks. It works because people are not random: taste comes in patterns, and once a system has spotted the patterns it can fill a gap by noticing who else shares them. The catch is that the blanks are not accidental — people skip things for reasons, and the guesses quietly inherit that bias. Even so, this way of seeing the problem shaped most of the recommendation methods in use today.