J. Mareček, P. Richtárik, M. Takáč
Lecture Notes in Computer Science, ECML-PKDD, (2018)
Matrix completion is a well-known problem: Given dimensions of a matrix X and some of its elements Xi,j, (i,j)∈ E, the goal is to find the remaining elements. Without imposing any further requirements on X , there are infinitely many solutions. In many applications, however, the matrix completion that minimizes the rank:
min Y rank(Y), subject to Yi,j=Xi,j, (i,j)∈E,
often works as well as the best known solvers for problems in the particular domain. There are literally hundreds of applications of matrix completion, especially in recommender systems , where the matrix is composed of ratings, with a row per user and column per product.