### Abstract

Let M be an nα × n matrix of rank r « n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(rn) observed entries with relative root mean square error RMSE ≤ C(α) (nr/|E|)^{1/2}. Further, if r = O(1) and M is sufficiently unstructured, then it can be reconstructed exactly from |E| = O(n log n) entries. This settles (in the case of bounded rank) a question left open by Candès and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log n), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemerédi and Feige-Ofek on the spectrum of sparse random matrices.

Original language | English (US) |
---|---|

Title of host publication | 2009 IEEE International Symposium on Information Theory, ISIT 2009 |

Pages | 324-328 |

Number of pages | 5 |

DOIs | |

State | Published - Nov 19 2009 |

Event | 2009 IEEE International Symposium on Information Theory, ISIT 2009 - Seoul, Korea, Republic of Duration: Jun 28 2009 → Jul 3 2009 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

ISSN (Print) | 2157-8102 |

### Other

Other | 2009 IEEE International Symposium on Information Theory, ISIT 2009 |
---|---|

Country | Korea, Republic of |

City | Seoul |

Period | 6/28/09 → 7/3/09 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Matrix completion from a few entries'. Together they form a unique fingerprint.

## Cite this

*2009 IEEE International Symposium on Information Theory, ISIT 2009*(pp. 324-328). [5205567] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2009.5205567