Appears in collection : Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme

Let X be a n_1-by-n_2 matrix with entries in GF(2) and rank r<min(n_1,n_2). We consider the problem of reconstructing X given only a subset of its entries. This problem has recently found numerous applications, most notably in network and index coding, where finding optimal linear codes (over some field GF(q) can be reduced to finding the minimum rank completion of a matrix with a subset of revealed entries. The problem of matrix completion over reals also has many applications and in recent years several polynomial-time algorithms with provable recovery guarantees have been developed. However, to date, such algorithms do not exist in the finite-field case. We propose a linear algebraic algorithm, based on inferring low-weight relations among the rows and columns of X, to attempt to complete X given a random subset of its entries. We establish conditions on the row and column spaces of X under which the algorithm runs in polynomial time and can successfully complete X with high probability from a vanishing fraction of its entries. We then propose a linear programming-based extension of our basic algorithm, and evaluate it empirically. Our simulations suggest that this linear programming-based method can successfully complete n-by-n random rank r matrices (for n<100 and r<10) from at most 3log N_{n,r} entries where N_{n,r} is the cardinality of the set of n-by-n binary matrices of rank r. Joint work with James Saunderson and Maryam Fazel.