Matrix Factorization & ALS

Low-Rank Matrix Decomposition

Given sparse interaction matrix $R \in \mathbb{R}^{U \times I}$ where most entries are un-observed:

$$R \approx P \cdot Q^T$$

• $P \in \mathbb{R}^{U \times k}$: Dense User Latent Matrix (row $p_u \in \mathbb{R}^k$).
• $Q \in \mathbb{R}^{I \times k}$: Dense Item Latent Matrix (row $q_i \in \mathbb{R}^k$).
• $k \ll \min(U, I)$: Latent dimension size (e.g., $k = 64\text{--}256$).

  Sparse Rating Matrix R (U × I)               User Embeddings P (U × k)    Item Embeddings Q^T (k × I)
  ┌───┬───┬───┬───┐                            ┌───┬───┐                    ┌───┬───┬───┬───┐
  │ 5 │ ? │ 1 │ ? │                            │.1 │.8 │                    │.4 │.2 │.9 │.1 │
  ├───┼───┼───┼───┤            ≈               ├───┼───┤         ×          ├───┼───┼───┼───┤
  │ ? │ 4 │ ? │ 2 │                            │.9 │.3 │                    │.7 │.6 │.1 │.8 │
  └───┴───┴───┴───┘                            └───┴───┘                    └───┴───┴───┴───┘

Predicted Rating with Biases:

$$\hat{R}_{ui} = \mu + b_u + b_i + p_u^T q_i$$

• $\mu$: Global average rating across all users and items.
• $b_u$: User bias (some users systematically rate higher or lower).
• $b_i$: Item bias (popular movies receive higher average scores).

Alternating Least Squares (ALS) vs SGD

Objective Loss with L2 Regularization $\lambda$:

$$\mathcal{L} = \sum_{(u,i) \in \text{Observed}} \left( R_{ui} - (\mu + b_u + b_i + p_u^T q_i) \right)^2 + \lambda \left( \|p_u\|_2^2 + \|q_i\|_2^2 + b_u^2 + b_i^2 \right)$$

Because $p_u^T q_i$ multiplies two unknown matrices, the loss is non-convex jointly.

ALS Optimization Loop:

1. Fix $Q$: Loss becomes strictly quadratic in $P$. Solve for each user $p_u$ in parallel via closed-form linear algebra:

$$p_u = \left( Q^T Q + \lambda I \right)^{-1} Q^T R_{u,*}$$

2. Fix $P$: Loss becomes strictly quadratic in $Q$. Solve for each item $q_i$ in parallel:

$$q_i = \left( P^T P + \lambda I \right)^{-1} P^T R_{*,i}$$

3. Repeat until convergence!

Say this out loud

"Matrix Factorization decomposes sparse user-item interaction matrices R into dense low-rank user embeddings P and item embeddings Q. Preference predictions are computed via dot product R̂_ui = μ + b_u + b_i + p_u^T q_i. Alternating Least Squares (ALS) optimizes MF efficiently on distributed Spark clusters by alternating between solving P and Q in closed-form."

Follow-ups to expect

• How does iALS handle Implicit Feedback (Hu, Koren, Volinsky)? Replaces binary ratings with preference $p_{ui} \in \{0, 1\}$ and confidence weight $c_{ui} = 1 + \alpha r_{ui}$, solving $\min_{P,Q} \sum c_{ui} (p_{ui} - p_u^T q_i)^2 + \lambda \|P\|_F^2$.
• How does Matrix Factorization handle Cold-Start Users? Pure MF fails on new users with zero interaction history ($N=0$). Cold-start requires hybrid models incorporating user demographics and item content features (Two-Tower networks).