Pages: 460-467

Low rank matrix completion is the problem of recovering the missing entries of a large data matrix by using the low-rankness assumption. Much attention has been put recently to exploiting correlations between the column/row entities, through side information or data adaptive models, to improve the matrix completion quality. In this paper, we propose a novel graph learning algorithm and apply it to the learning of a graph adjacency matrix from a given, incomplete datamatrix,inawaysuchthattheweightedgraphedgesencode pairwise similarities between the rows/columns of the data matrix. Subsequently we present a graph-regularized low-rank matrix completion method. Experiments on synthetic and real datasets show that this regularized matrix completion approach achieves significant improvement for the matrix completion task.