Simple algorithms and guarantees for low rank matrix completion over F_2

Abstract

Let X* be a n_1 × n_2 matrix with entries in F_2 and rank r <; min(n_1, n_2) (often 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 Fq) 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.

Additional details