Recommender Systems and Matrix Factorization

When a streaming app suggests a drama you end up loving, or an online shop shows exactly the shoes you were about to search for, a recommender system is at work. Behind many of these systems sits an elegant idea from linear algebra: a huge, mostly empty table of ratings can be approximated by the product of two thin matrices. This article explains that idea, matrix factorization, and computes predictions and training updates by hand.

The Ratings Matrix

Imagine \( m \) users and \( n \) items (films, products, songs). Arrange their ratings in an \( m \times n \) matrix \( R \), where \( r_{ui} \) is user \( u \)'s rating of item \( i \), say on a 1 to 5 scale.

The defining feature of \( R \) is that it is sparse: a typical user has rated only a tiny fraction of the catalogue. On a platform with millions of users and tens of thousands of items, often well over 99% of entries are missing. The recommendation problem is to fill in the blanks sensibly, then show each user the items with the highest predicted ratings.

Two Families of Approaches

• Content-based filtering uses item features (genre, price, brand) and recommends items similar to those a user liked before.
• Collaborative filtering uses only the pattern of ratings: if users who agree with you on many items liked something you have not seen, you will probably like it too.

A simple collaborative method compares users with cosine similarity. If Ali rated three films \( (5, 4, 1) \) and Sara rated them \( (4, 5, 2) \), then

$$ \cos\theta = \frac{5(4) + 4(5) + 1(2)}{\sqrt{25 + 16 + 1}\,\sqrt{16 + 25 + 4}} = \frac{42}{\sqrt{42}\sqrt{45}} \approx \frac{42}{6.481 \times 6.708} \approx 0.966 , $$

so their tastes are very similar. Neighbour methods like this are intuitive but scale poorly and struggle when users share few rated items. Matrix factorization handles both problems better.

The Latent Factor Model

The key assumption is that tastes are driven by a small number \( k \) of hidden, or latent, factors. For films these might loosely correspond to "amount of action", "seriousness" or "romance", although the model discovers them from data and they need not have neat labels.

Each user \( u \) gets a vector \( \mathbf{p}_u \in \mathbb{R}^k \) saying how much they like each factor, and each item \( i \) gets a vector \( \mathbf{q}_i \in \mathbb{R}^k \) saying how much it has of each factor. The predicted rating is their dot product:

$$ \hat{r}_{ui} = \mathbf{p}_u^\top \mathbf{q}_i = \sum_{f=1}^{k} p_{uf}\, q_{if}. $$

Stacking the vectors as rows of \( P \) (size \( m \times k \)) and \( Q \) (size \( n \times k \)) gives the whole predicted matrix at once:

$$ \hat{R} = P Q^\top . $$

With \( m = 100{,}000 \) users, \( n = 10{,}000 \) items and \( k = 50 \), the full matrix has \( 10^9 \) entries, but \( P \) and \( Q \) together store only \( 50 \times 110{,}000 = 5{,}500{,}000 \) numbers. Factorization is a massive compression.

Worked Example 1: Predicting Ratings and Measuring Error

Take \( k = 2 \), three users and three films. Suppose training has produced

$$ P = \begin{pmatrix} 1.5 & 0.2 \\ 0.3 & 1.4 \\ 1.0 & 1.0 \end{pmatrix} \begin{matrix} \leftarrow \text{Ali} \\ \leftarrow \text{Sara} \\ \leftarrow \text{Bilal} \end{matrix}, \qquad Q = \begin{pmatrix} 2.0 & 0.5 \\ 0.4 & 2.5 \\ 1.5 & 1.5 \end{pmatrix} \begin{matrix} \leftarrow \text{Action film} \\ \leftarrow \text{Drama} \\ \leftarrow \text{Comedy} \end{matrix}. $$

Step 1. Compute predictions. For Ali and the action film: \( 1.5(2.0) + 0.2(0.5) = 3.0 + 0.1 = 3.1 \). Repeating for every pair:

$$ \hat{R} = PQ^\top = \begin{pmatrix} 3.10 & 1.10 & 2.55 \\ 1.30 & 3.62 & 2.55 \\ 2.50 & 2.90 & 3.00 \end{pmatrix}. $$

For instance, Sara and the drama: \( 0.3(0.4) + 1.4(2.5) = 0.12 + 3.5 = 3.62 \).

Step 2. Compare with known ratings. Suppose the observed ratings are Ali: action 3, drama 1; Sara: action 1, drama 4; Bilal: comedy 4. The errors \( \hat{r} - r \) are

• Ali–action: \( 3.10 - 3 = 0.10 \)
• Ali–drama: \( 1.10 - 1 = 0.10 \)
• Sara–action: \( 1.30 - 1 = 0.30 \)
• Sara–drama: \( 3.62 - 4 = -0.38 \)
• Bilal–comedy: \( 3.00 - 4 = -1.00 \)

Step 3. Root mean squared error. Squares: \( 0.01, 0.01, 0.09, 0.1444, 1 \), summing to \( 1.2544 \). Then

$$ \text{RMSE} = \sqrt{\frac{1.2544}{5}} = \sqrt{0.25088} \approx 0.501 . $$

Step 4. Recommend. The blank entries are now filled. Ali's unseen comedy is predicted at 2.55 and Sara's unseen comedy also at 2.55, so neither is a strong recommendation; Bilal's unseen drama at 2.90 is his best remaining option.

Training the Factors

We learn \( P \) and \( Q \) by minimising squared error over the observed ratings only, with L2 regularization to prevent overfitting:

$$ \min_{P, Q} \sum_{(u,i)\,\text{observed}} \left(r_{ui} - \mathbf{p}_u^\top \mathbf{q}_i\right)^2 + \lambda\left(\lVert \mathbf{p}_u \rVert^2 + \lVert \mathbf{q}_i \rVert^2\right). $$

Ignoring missing entries is essential: treating them as zeros would teach the model that everyone hates everything they have not rated.

Stochastic gradient descent loops over observed ratings. For each one, compute the error \( e_{ui} = r_{ui} - \hat{r}_{ui} \) and update (absorbing a factor of 2 into the learning rate \( \eta \)):

$$ \mathbf{p}_u \leftarrow \mathbf{p}_u + \eta\left(e_{ui}\, \mathbf{q}_i - \lambda \mathbf{p}_u\right), \qquad \mathbf{q}_i \leftarrow \mathbf{q}_i + \eta\left(e_{ui}\, \mathbf{p}_u - \lambda \mathbf{q}_i\right). $$

Both updates use the old values of \( \mathbf{p}_u \) and \( \mathbf{q}_i \).

Worked Example 2: One SGD Update

A user has \( \mathbf{p} = (1.2, 0.8) \) and an item has \( \mathbf{q} = (1.5, 0.5) \). The true rating is \( r = 4 \). Use \( \eta = 0.1 \) and \( \lambda = 0.02 \).

Step 1. Prediction. \( \hat{r} = 1.2(1.5) + 0.8(0.5) = 1.8 + 0.4 = 2.2 \).

Step 2. Error. \( e = 4 - 2.2 = 1.8 \).

Step 3. Update the user vector.

• \( e\,\mathbf{q} - \lambda \mathbf{p} = (1.8 \times 1.5 - 0.02 \times 1.2,\; 1.8 \times 0.5 - 0.02 \times 0.8) = (2.7 - 0.024,\; 0.9 - 0.016) = (2.676,\; 0.884) \)
• \( \mathbf{p}_{\text{new}} = (1.2 + 0.2676,\; 0.8 + 0.0884) = (1.4676,\; 0.8884) \)

Step 4. Update the item vector (using the old \( \mathbf{p} \)).

• \( e\,\mathbf{p} - \lambda \mathbf{q} = (1.8 \times 1.2 - 0.02 \times 1.5,\; 1.8 \times 0.8 - 0.02 \times 0.5) = (2.16 - 0.03,\; 1.44 - 0.01) = (2.13,\; 1.43) \)
• \( \mathbf{q}_{\text{new}} = (1.5 + 0.213,\; 0.5 + 0.143) = (1.713,\; 0.643) \)

Step 5. Check the improvement. \( \hat{r}_{\text{new}} = 1.4676(1.713) + 0.8884(0.643) \approx 2.514 + 0.571 = 3.085 \). The prediction moved from 2.2 to about 3.09, much closer to 4, after a single step. Repeating over millions of ratings for several passes gradually shapes all the factor vectors.

An alternative training method, alternating least squares (ALS), fixes \( Q \) and solves a ridge regression for each user exactly, then fixes \( P \) and solves for each item, and repeats. It parallelises well on large clusters.

Making the Model Realistic

Practical systems add bias terms, because some users rate everything generously and some films are simply popular:

$$ \hat{r}_{ui} = \mu + b_u + b_i + \mathbf{p}_u^\top \mathbf{q}_i , $$

where \( \mu \) is the global average rating, \( b_u \) the user's tendency and \( b_i \) the item's. Other refinements include:

• Implicit feedback: clicks, views and purchases instead of explicit stars, usually weighted by confidence.
• The cold-start problem: new users or items have no ratings, so systems fall back on content features or popularity until data arrive.
• Evaluation: besides RMSE, ranking metrics such as precision at \( k \) measure whether the top few suggestions are actually good.

Matrix factorization is also closely related to the singular value decomposition (SVD), which gives the best rank-\( k \) approximation of a complete matrix. Recommender "SVD" methods adapt this idea to matrices with missing entries.

Did You Know?

• The Netflix Prize (2006 to 2009) offered one million US dollars for a 10% improvement in rating-prediction RMSE, and matrix factorization methods were central to the winning solutions.
• Latent factors learned from ratings alone often line up with recognisable genres, even though the model was never told any genre labels.
• Modern systems often combine factorization ideas with deep neural networks that also use text, images and browsing sequences.

Key Takeaways

• Ratings form a huge, sparse matrix; recommendation means predicting its missing entries.
• Matrix factorization approximates \( R \approx PQ^\top \), with each rating predicted by a dot product of user and item vectors.
• Training minimises regularised squared error over observed ratings only, using SGD or alternating least squares.
• One SGD step nudges both vectors in the direction that reduces the prediction error.
• Bias terms, implicit feedback and cold-start strategies make the basic model work in practice.

Working on a recommender system project or a linear algebra assignment? Amathify's experts and PhD scholars give step-by-step solutions; reach us on WhatsApp or through the Ask a Question form.