Matrix Factorization

Overview

Matrix factorization decomposes the user-item interaction matrix R (m×n) into two low-rank matrices: U (m×k) and V (n×k), where k << min(m,n). Predicted rating: r̂ᵢⱼ = uᵢ · vⱼ. Trains in O(k × nnz × iterations) where nnz = non-zero entries.

When to Use

Trigger conditions:

• Scaling CF beyond pairwise similarity (millions of users/items)
• Discovering latent factors that explain user-item interactions
• Predicting ratings for unobserved user-item pairs

When NOT to use:

• When interaction data is extremely sparse (< 0.1% fill) — insufficient for learning
• When you need real-time updates (retraining is expensive)

Algorithm