CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20170127-135215938

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170127-135215938

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ISIT.2016.7541266 DOIArticle
http://ieeexplore.ieee.org/document/7541266/PublisherArticle
Additional Information:© 2016 IEEE. This is based on work supported by the NSF under grant CCF-1409836.
Funders:
Funding AgencyGrant Number
NSFCCF-1409836
Record Number:CaltechAUTHORS:20170127-135215938
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170127-135215938
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7541266&isnumber=7541040
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73783
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:27 Jan 2017 22:25
Last Modified:03 Oct 2019 16:31

Repository Staff Only: item control page