Candidate Generation & Matrix Factorization¶
Candidate generation is optimized for recall + speed: billions → thousands in under 50 ms. We don't want to miss any good item; precision is ranking's job. This page builds the first great candidate generator — matrix factorization — from the sparse interaction matrix through its math, its two solvers, implicit feedback, sparse storage and horizontal scaling, and the connections and distinctions to PCA and LoRA.
Rapid Recall
The interaction matrix \(R\) (users × items) is catastrophically sparse; the recommendation problem is "fill in the blanks." MF assumes \(R\) is low-rank and factorizes it as \(\hat R = PQ^\top\), fitting the dot products \(p_u\cdot q_i\) to observed cells only with L2 regularization. Solve by SGD (Funk SVD) or ALS (embarrassingly parallel, the production favorite). Add bias terms \(\mu + b_u + b_i\). For implicit feedback, model preference weighted by confidence. Serve by dumping frozen item vectors into an ANN index and doing MIPS against the user vector. You never store the dense matrix (it would be petabytes) — only the observed triples, then two skinny dense vector tables. MF is not PCA (missing data forbids the covariance step) and only rhymes with LoRA (both exploit low intrinsic rank, but MF factorizes the target matrix while LoRA factorizes a delta on a frozen one).
§1 Vocabulary: CF is not matrix factorization¶
Vocabulary precision
CF ≠ matrix factorization. CF is the family (recommend by behavioral co-occurrence). Matrix factorization is one algorithm within it. There is also neighborhood-based CF (user–user, item–item similarity) which came first. MF is the one that scaled and won, so people sloppily equate them. Keep the distinction.
§2 The setup — the interaction matrix R¶
Rows = users (say 100M). Columns = items (say 10M). Cell \(R_{u,i}\) = the interaction: a rating (1–5, old Netflix) or implicit (1 = watched, blank = didn't). The matrix is catastrophically sparse — a user touches a few hundred of 10M items, so >99.99% of cells are empty.
The recommendation problem stated bluntly: fill in the blanks. Predict the empty cells; the highest predictions become recommendations.
§3 Matrix factorization — the math, start to end¶
The matrix is secretly low-rank. Tastes are driven by a small number of latent factors — maybe 50–200, not millions. The claim: \(R\) can be approximated as a product of two much smaller matrices.
- P = user matrix, shape \((100\text{M} \times k)\). Each user gets a \(k\)-dim vector.
- Q = item matrix, shape \((10\text{M} \times k)\). Each item gets a \(k\)-dim vector.
Prediction = dot product:
Each of the \(k\) dimensions is a latent factor (e.g. "amount of action"). If user \(u\) scores high on it AND item \(i\) scores high on it, that term contributes a lot. The dot product is high when preferences align with properties across all \(k\) factors.
Full reconstruction in matrix form:
\(P\) is (100M × k), \(Q^\top\) is (k × 10M), product is (100M × 10M). The single-cell version is one entry of this product. Nobody labels the dimensions — the model discovers latent factors on its own.
How you learn P and Q¶
Fit the dot products to the observed cells only:
For every cell we actually have data for, make the dot product match (squared error). The \(\lambda\) term is L2 regularization — without it the vectors overfit the sparse data and explode.
The sum runs over observed cells only
A blank means "unknown," not "rating zero." This is the single most important line in MF: you never fit the dot product to a blank. The blanks are what you are predicting, not data you are fitting to.
Two solvers¶
- SGD — for each observed cell, compute error, nudge \(p_u\) and \(q_i\) down the gradient. This is Simon Funk's "Funk SVD" from the Netflix Prize. Sequential.
- ALS (Alternating Least Squares) — fix \(Q\); solving for \(P\) is plain convex least-squares (closed form). Then fix \(P\), solve \(Q\). Alternate. Embarrassingly parallel → the production favorite (Spark MLlib).
Name trap — 'SVD' in RecSys ≠ SVD the operation
True SVD requires a fully filled matrix; it has no notion of missing entries. Our matrix is 99.99% missing, so classical SVD is literally inapplicable. The Netflix-era "SVD" is learned factorization on observed entries only via SGD/ALS. Same low-rank spirit, completely different mechanism.
Bias terms — the practical refinement¶
\(\mu\) = global average, \(b_u\) = this user's tendency (generous rater?), \(b_i\) = this item's tendency (universally loved?). The dot product captures the personalized residual — this specific user's fit with this specific item after baselines. In the Netflix Prize, bias terms alone got you shockingly far.
Implicit feedback — what modern systems actually use¶
Almost nobody has explicit 1–5 ratings at scale. You have clicks/watches/purchases — implicit feedback. This breaks the clean formulation:
- No negatives — a blank means "never saw it," not "disliked." You can't treat unobserved as negative, but all signal is positive-only otherwise.
- The fix (Hu, Koren, Volinsky 2008): split into preference (interacted: 1/0) weighted by confidence (watched once vs. ten times). Sum over all cells, weighting observed ones much higher.
Serving — how MF meets the 50 ms goal¶
After training, every item has a frozen vector \(q_i\). Offline, dump all 10M item vectors into an ANN index. Online: fetch \(p_u\), and candidate generation = find items with highest dot product to \(p_u\) = approximate nearest-neighbor search.
The wall MF hits → why two-tower replaced it
MF's vectors are learned purely from the ID and the interaction matrix. So: (1) Cold start — new item → no \(q_i\); new user → no \(p_u\). (2) Can't ingest side features — it only knows the user ID, not "25, Hyderabad, mobile, evening." Two-tower fixes both by replacing the lookup-vector with a feature-eating neural net.
§4 Storage & scaling — is this a compute disaster?¶
A dense 100M × 10M float matrix = 4 petabytes. Physically absurd. Nobody ever stores it. The "matrix" is a conceptual object; storage is entirely sparse.
What you actually store¶
Only the observed cells — ~10–50 billion triples, 3–4 orders of magnitude smaller than the dense form. Each entry is essentially (user_id, item_id, value). Emptiness costs nothing because you don't represent it.
| Layout | Optimized for | Use |
|---|---|---|
| COO (coordinate list) | list of (u,i,v) triples | building incrementally / streaming new interactions |
| CSR (compressed sparse row) | "all items user u touched" | training that iterates user-by-user |
| CSC (compressed sparse column) | "all users who touched item i" | item-by-item passes (ALS item step, item-item sim) |
Your "dict of user → {item: rating}" is the adjacency-list / bipartite-graph view — conceptually identical to CSR, which is just the cache-friendly array-packed version. scipy.sparse converts between them per access pattern.
The reframe that dissolves the worry
The sparse matrix is the training input. Once MF finishes, you throw the matrix away for serving. You keep: P = 100M × 100 × 4B = 40 GB, Q = 10M × 100 × 4B = 4 GB. The entire model is ~44 GB of skinny dense vectors. The "petabyte matrix" never persisted.
Vertical or horizontal scaling?¶
Horizontal, almost always — and the algorithm forces the choice:
- ALS parallelizes cleanly. With \(Q\) fixed, every user's vector solves independently — no user update depends on another, they share only read-only \(Q\). Shard users across 1000 machines, broadcast \(Q\), solve in parallel; then flip for items. Embarrassingly parallel → Spark MLlib uses ALS.
- SGD resists parallelism. It updates \(p_u\) and \(q_i\) together per cell, sequentially; concurrent updates to the same popular item's vector race. Parallelizable (Hogwild!, parameter servers) but takes real engineering.
- Why not vertical? Biggest single box still can't hold 50B interactions + do the linear algebra in reasonable wall-clock. Vertical shows up only in pieces (e.g., the ANN serving index wants RAM-heavy machines).
One-line systems summary: store interactions sparsely (triples → CSR/CSC), train with a horizontally-parallel algorithm (ALS), then discard the matrix and serve from two dense vector tables + an ANN index.
§5 MF vs LoRA, and why not PCA?¶
MF vs LoRA — same math object, opposite purpose¶
Both are low-rank factorizations of a big matrix into two skinny ones. The difference is what the low-rank thing is.
MF — the low-rank product IS the matrix; \(R\) is built from scratch out of \(P\) and \(Q\). LoRA — \(W_0\) is a big frozen pretrained matrix; \(BA\) is a low-rank DELTA added on top. MF reconstructs a matrix; LoRA corrects a frozen one.
Shared DNA: both bet a useful big matrix has low intrinsic rank. MF bets the interaction matrix is low-rank (tastes = few factors). LoRA bets the weight update during finetuning is low-rank.
What to say (and not say)
Don't say "MF is basically LoRA" — it reads as pattern-matching, because the purpose is inverted. Say: "Both exploit low intrinsic rank, but MF factorizes the target matrix itself while LoRA factorizes a delta on a frozen pretrained matrix." Also current for 2026: LoRA/QLoRA do appear in RecSys — when finetuning an LLM as a recommender or reranker — but in the LLM-for-recsys branch, not in classical MF.
Why not just run PCA / SVD on the matrix?¶
You correctly intuited "if it's low-rank, take the top-k principal components." The blocker is one word: missing data.
PCA's first step computes the covariance matrix — for every pair of items, how they co-vary across all users. Each term needs both \(R_{u,i}\) and \(R_{u,j}\) present. With 99.99% blanks, almost every covariance term is undefined → no covariance → no eigendecomposition → no PCA. (PCA = SVD on the centered matrix, so "why not PCA" and "why not SVD" have the identical answer.)
And imputing the blanks corrupts everything:
- Fill with 0 → asserts "didn't watch = hates it." False. PCA then finds the components of a matrix that is mostly a lie.
- Fill with mean → injects billions of synthetic constants; variance gets swamped by imputed values.
- Fill with anything → you're imputing the very thing you're trying to predict. Circular.
The deep distinction
PCA/SVD: complete the matrix, then factorize. The completion step is forced and corrupting. MF: never complete it — fit P,Q to observed cells only, and the dot products on the blanks ARE the recommendations. The blanks flip from "a problem PCA must paper over" to "the answer MF produces." Your low-rank premise was correct; the obstacle was never the rank, it was observability.
Interview questions¶
Q1: Why can't you run classical SVD/PCA directly on the interaction matrix? SVD/PCA require a complete matrix — PCA's first step is the covariance matrix, where each term needs both cell values present. With 99.99% blanks, covariance is undefined; no covariance → no eigendecomposition. Imputing blanks corrupts everything (0 = "hates it" is a lie; mean swamps real variance). MF instead fits \(P,Q\) to observed cells only and the dot products on blanks ARE the predictions.
Q2: In implicit feedback, what's wrong with treating every blank as a "0 = dislike" label? A blank means "never saw it / no chance," not "disliked." Labeling it 0 asserts a negative preference that isn't there. The fix: model preference (1/0) weighted by confidence (interaction strength), summing over all cells but weighting observed ones much higher.
Q3: What does the bias-term decomposition (μ + b_u + b_i + p_u·q_i) separate? \(\mu\) = global average; \(b_u\) = the user's overall tendency (generous/harsh rater); \(b_i\) = the item's overall tendency (universally loved/hated); the dot product = the personalized residual, this specific user's fit with this specific item after removing the baselines.
Q4: Why does ALS benefit from horizontal scaling while SGD fights it? With \(Q\) fixed, ALS solves every user's vector independently — no user update depends on another, they share only read-only \(Q\) — so you shard users across machines and solve in parallel (embarrassingly parallel). SGD updates \(p_u\) and \(q_i\) together per cell sequentially; concurrent updates to the same popular item's vector race, so parallelism takes careful engineering.