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 .
http://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: http://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: |
| |||||||||

Additional Information: | © 2016 IEEE. This is based on work supported by the NSF under grant CCF-1409836. | |||||||||

Funders: |
| |||||||||

Record Number: | CaltechAUTHORS:20170127-135215938 | |||||||||

Persistent URL: | http://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: | 27 Jan 2017 22:25 |

Repository Staff Only: item control page