Matrix factorisation

Objective#

The standard regularised formulation, following Koren, Bell and Volinsky (2009):

$$ \min_{P, Q, b_*} \sum_{(u,i) \in \mathcal{K}} \left( r_{ui} - \mu - b_u - b_i - \mathbf{p}_u^\top \mathbf{q}_i \right)^2 + \lambda \left( |\mathbf{p}_u|^2 + |\mathbf{q}_i|^2 + b_u^2 + b_i^2 \right) $$

Where:

• $\mathcal{K}$ — the set of observed $(u,i)$ pairs. The sum runs over observations only, never over the full grid.
• $\mu \in \mathbb{R}$ — the global mean rating.
• $b_u, b_i \in \mathbb{R}$ — user and item bias terms.
• $\mathbf{p}_u \in \mathbb{R}^k$, $\mathbf{q}_i \in \mathbb{R}^k$ — the latent factor vectors, $k \ll \min(|U|, |I|)$.
• $\lambda > 0$ — the regularisation strength.

Why this is not SVD#

The name "SVD" attached itself to this family and is misleading. The truncated singular value decomposition minimises reconstruction error over all entries of a fully observed matrix, and has a unique solution given by the top singular triplets.

Here the sum runs over $\mathcal{K}$ only. Restricting the loss to observed entries makes the problem non-convex in $(P, Q)$ jointly, destroys the orthogonality structure, and removes uniqueness — the objective is invariant under $P \mapsto PA$, $Q \mapsto Q A^{-\top}$ for any invertible $A \in \mathbb{R}^{k \times k}$. Only the product $PQ^\top$ is identified, which is why individual factors have no stable interpretation across runs.

It is convex in $P$ with $Q$ fixed, and vice versa. That is exactly what ALS exploits.

Two optimisers#

SGD (the code above). For each observation, with $e_{ui} = r_{ui} - \hat{r}_{ui}$:

$$ \mathbf{p}_u \leftarrow \mathbf{p}u + \gamma\,(e{ui}\,\mathbf{q}_i - \lambda \mathbf{p}_u), \qquad \mathbf{q}_i \leftarrow \mathbf{q}i + \gamma\,(e{ui}\,\mathbf{p}_u - \lambda \mathbf{q}_i) $$

Cost per epoch: $O(|\mathcal{K}| k)$. Simple, memory-light, and the standard choice for explicit-feedback data.

ALS. Fix $Q$ and solve for each $\mathbf{p}_u$ in closed form:

$$ \mathbf{p}u = \left( Q{I_u}^\top Q_{I_u} + \lambda \mathbf{I}k \right)^{-1} Q{I_u}^\top \mathbf{r}_u $$

Where $Q_{I_u}$ stacks the factor rows of the items $u$ rated. Each user solve is independent, so ALS parallelises across a cluster with no communication between solves. Cost per sweep: $O(|\mathcal{K}| k^2 + (|U| + |I|) k^3)$. ALS is the standard choice for implicit feedback, where every cell participates and SGD over $|U| \times |I|$ is infeasible — see Hu, Koren and Volinsky (2008) and implicit feedback.

Extensions that mattered#

SVD++ (Koren, 2008) adds an implicit-feedback term to the user representation:

$$ \hat{r}_{ui} = \mu + b_u + b_i + \mathbf{q}_i^\top \left( \mathbf{p}u + |N(u)|^{-1/2} \sum{j \in N(u)} \mathbf{y}_j \right) $$

$N(u)$ is the set of items $u$ interacted with regardless of rating value, and $\mathbf{y}_j$ is a second item factor learned for that purpose. The insight is that which items a user chose to rate carries information independent of how they rated them. This was one of the largest single gains in the Netflix Prize.

timeSVD++ (Koren, 2009) makes $b_u$, $b_i$ and $\mathbf{p}_u$ functions of time, capturing rating drift and item ageing.

BPR-MF (Rendle et al., 2009) replaces squared error with a pairwise ranking loss, optimising $P(i \succ j \mid u)$ over sampled positive-negative pairs. This is the correct objective when the product is a ranked list rather than a predicted score.

The 2020 correction#

Neural Collaborative Filtering (He et al., 2017) argued that replacing the dot product $\mathbf{p}_u^\top \mathbf{q}_i$ with a learned MLP over $[\mathbf{p}_u; \mathbf{q}_i]$ improves accuracy.

Rendle, Krichene, Zhang and Anderson (2020), Neural Collaborative Filtering vs. Matrix Factorization Revisited, re-ran the comparison with matched tuning effort. A properly regularised dot product matched or beat the learned similarity on the same benchmarks, and the MLP needed far more capacity to approximate a dot product than to use one. They also showed the dot product's inner-product structure is what makes efficient retrieval possible at all.

The practical reading: a well-tuned matrix factorisation is a serious baseline in 2026, not a historical footnote. Deep models earn their place through features — context, sequence, side information, multi-task objectives — rather than through replacing the interaction function.

Cost summary#

Because scores are inner products, item factors can be indexed with maximum inner product search and retrieval becomes sublinear. That property is inherited by two-tower models and is the reason the field kept the dot product.

Papers#

• Funk (2006), Netflix Update: Try This at Home — the original blog post, still worth reading.
• Koren (2008), Factorization Meets the Neighborhood (SVD++), KDD.
• Hu, Koren and Volinsky (2008), Collaborative Filtering for Implicit Feedback Datasets, ICDM.
• Rendle et al. (2009), BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI.
• Koren, Bell and Volinsky (2009), Matrix Factorization Techniques for Recommender Systems, IEEE Computer.
• Rendle et al. (2020), Neural Collaborative Filtering vs. Matrix Factorization Revisited — arxiv.org/abs/2005.09683

What to learn next#

• Implicit feedback — the ALS variant and the confidence weighting it needs.
• Two-tower retrieval models — factorisation with learned encoders.
• Ranking metrics — evaluating the list rather than the score.