Low rank matrix completion and realization of graphs: results and problems
This is an incremental survey that addresses theoretical extensions of matrix completion for applications in graph theory.
The paper surveys a generalization of the Netflix matrix completion problem, where instead of known matrix entries, linear relations on elements are given, and applies these results to graph embeddings in surfaces.
The Netflix problem (from machine learning) asks the following. Given a ratings matrix in which each entry $(i,j)$ represents the rating of movie $j$ by customer $i$, if customer $i$ has watched movie $j$, and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next. The remaining entries are predicted so as to minimize the {\it rank} of the completed matrix. In this survey we study a more general problem, in which instead of knowing specific matrix elements, we know linear relations on such elements. We describe applications of these results to embeddings of graphs in surfaces (more precisely, embeddings with rotation systems, and embeddings modulo 2).