Simple algorithms and guarantees for low rank matrix completion over F₂

Let X^∗ be a n₁ × n₂ matrix with entries in F₂ and rank r <min(n₁, n₂) (often r ≪ min(n₁, n₂)). 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 F_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 (in the size of X^∗) 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.