A Caltech Library Service

Simple algorithms and guarantees for low rank matrix completion over F_2

Saunderson, James and Fazel, Maryam and Hassibi, Babak (2016) Simple algorithms and guarantees for low rank matrix completion over F_2. In: 2016 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 86-90. ISBN 978-1-5090-1806-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2016 IEEE. This is based on work supported by the NSF under grant CCF-1409836.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20170127-135215938
Persistent URL:
Official Citation:J. Saunderson, M. Fazel and B. Hassibi, "Simple algorithms and guarantees for low rank matrix completion over F2," 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, 2016, pp. 86-90. doi: 10.1109/ISIT.2016.7541266 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73783
Deposited By: Tony Diaz
Deposited On:27 Jan 2017 22:25
Last Modified:03 Oct 2019 16:31

Repository Staff Only: item control page