MATH 2310: Lecture 15
Matrix Completion
Alex Townsend
In this lecture, we will explore the concept of matrix completion, a technique widely used in applications
such as collaborative filtering (e.g., recommendation systems), machine learning, and data analysis. Matrix
completion focuses on the problem of filling in missing entries of a matrix based on the known entries.
Netflix’s movie recommendation problem
Netflix’s movie recommendation problem is a classic example of matrix completion applied in collaborative
filtering. The fundamental challenge involves a large, partially observed user-movie rating matrix A, where
each entry Aij represents the rating given by user i to movie j. Since users have rated only a small subset of
the total movies, the matrix A contains numerous missing entries. The objective is to predict these missing
ratings to provide personalized movie recommendations to users who haven’t yet watched a movie.
Netflix prize
The Netflix Prize, launched in 2006, was a competition designed to improve Netflix’s movie recommendation
system by advancing matrix completion techniques. It made the problem famous. The goal of the challenge
was to predict user ratings for films based on a dataset of over 100 million ratings, where only a portion
of the ratings was known, leaving large sections of the user-movie matrix incomplete. Netflix offered a $1
million prize to any team that could improve their recommendation algorithm by at least 10% over Netflix’s
existing system. The challenge sparked significant interest and the “BellKor’s Pragmatic Chaos” team won
the prize over a year later.
The Matrix Completion Problem
Consider an m × n matrix A with some missing entries. The matrix completion problem involves finding the
missing entries in such a way that minimizes the rank of A.
1
For example, consider the 5 × 5 matrix given by
? ? −1 ? ?
? ? ? 1 ?
A= 1 1 ? 1 ?
1 ? 1 ? −1
? ? −1 ? ?
You could think of the rows as five people, and the columns as whether they like or dislike five vegetables in
their soup.
Since each ? can have a different values, you might like to think of this as:
a11 a12 −1 a14 a15
a21 a22 a23 1 a25
A= 1 1 a33 1 a35 ,
1 a42 1 a44 −1
a51 a52 −1 a54 a55
where a11 , a12 , a14 .a15 , a21 , a22 , a23 , a25 , a33 , a35 , a42 , a44 , a51 , a52 , a54 , and a55 are all the unknowns to find.
Question: Can you fill in the entries of A while ensuring that the final matrix is rank 1?
Step 1: Determine a basis for the range. If we know the final matrix is of rank 1, we know that
the columns of A will be multiples of each other. That is, we must have
A = a1 | a2 | a3 | a4 | a5 ,
where a2 , a3 , a4 , a5 are multiples of a1 .
Step 2: Write down all the equations and solve.
Looking at the ±1 entries in the third row of A, we see
a2 = a1 , a4 = a1 .
Looking that the ±1 entries in the fourth row, we see that
a3 = a1 , a5 = −a1 .
Now, we write down all the equations that we have, i.e., a2 = a1 , a4 = a1 , a3 = a1 , and a5 = −a1 :
a12 a11 a14 a11 −1 a11 a15 a11
a22 a21 1 a21 a23 a21 a25 a21
1 = 1 , 1 = 1 , a33 = 1 , a35 = − 1 .
a42 1 a44 1 1 1 −1 1
a52 a51 a54 a51 −1 a51 a55 a51
Now, you look around this long list of equations and solve them, in any order. I always try to solve for
the entries of a1 first because it tells me everything else immediately. Just by looking, we have a11 = −1,
a21 = 1, a51 = −1. Therefore, we know all the columns of A. The completed matrix is:
−1 −1 −1 −1 1 −1
1
1 1 1 −1 1
A= 1 1 1 1 −1 = 1 1 1 1 1 −1 .
1 1 1 1 −1 1
−1 −1 −1 −1 1 −1
I wrote the matrix as A = uvT because that is how I would store this final matrix in practice.
2
Matrix Completion problem as an optimization problem
The example above can be written as a mathematical problem. You first collect up the list of known entries
into a set. In our example above, we have the list of entries that we know as
Ω = {(3, 1), (4, 1), (3, 2), (1, 3), (4, 3), (5, 3), (2, 4), (3, 4), (4, 5)} .
This is because the (3, 1) entry is known as well as the (5, 3) entry, and so on.
The matrix completion problem is often written as
minimize rank(X)
Xij = Aij for (i, j) in Ω
This is the mathematical formulation of “finding a matrix with minimal rank that matches the known entries
of A.”
The main difference between the example above and the general matrix completion problem is the fol-
lowing: You are not told the rank of the completed matrix, only the fact that you want to minimize it.
Determining the rank in a matrix completion problem
Let’s solve the matrix completion problem for another matrix to see how it works when you are not told the
rank of the final matrix. For instance, consider the following incomplete product review ratings matrix:
5 4 9 10 8
3 ? 5 ? ?
A= ? ? ? 6 4
4 5 9 8 10
Since all the ? are different values, you might like to think of this as
5 4 9 10 8
3 a22 5 a24 a25
A= a31 a32 a33 6
,
4
4 5 9 8 10
where all the aij ’s are unknowns.
Step 0: Determine the rank of the completed matrix. Slowly increase the rank of the completed
matrix until you believe you could complete the matrix with that rank. Here, the completed matrix is not
going to be rank 0 because it cannot be the zero matrix. Likewise, it won’t be a rank one matrix because
column 1 and column 2 are not multiples of each other. Therefore, I’m going to see if I can complete the
matrix with a rank 2.
Exercises
1. Consider the following incomplete matrix:
1 ? 2
A = 4 6 ?
? 3 4
Solve the matrix completion problem with this matrix.
2. Consider the following incomplete matrix:
? 1 2 ?
4 ? ? 2
A=
1
1 2 2
? ? 1 2
Solve the matrix completion problem with this matrix.
3
3. Determine the rank of the matrix completion problem for these three examples:
1 ? 1 0 ? ? 1 ? 2
A1 = ? 2 2 , A2 = ? ? ? , A3 = ? 2 2
3 ? ? ? ? ? 3 ? ?
4. Consider the following incomplete matrix:
? 1 ?
A = ? 6 ?
? 3 4
Solve the matrix completion problem. Explain why the matrix completion problem has multiple
solutions. Can you give all the possible solutions.
