## Abstract

Let M be an nα × n matrix of rank r, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm, which we call OPTSPACE, that reconstructs M from |E| = O(r n) observed entries with relative root mean square error RMSE ≤ C (α) (nr/|E|)^{1/2} with probability larger than 1 - 1/n^{3} Further, if r = O(1) and M is sufficiently unstructured, then OPTSPACE reconstructs it exactly from |E| = O (n log n) entries with probability larger than 1 - 1/n ^{3}. 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) |
---|---|

Article number | 2046205 |

Pages (from-to) | 2980-2998 |

Number of pages | 19 |

Journal | IEEE Transactions on Information Theory |

Volume | 56 |

Issue number | 6 |

DOIs | |

State | Published - Jun 2010 |

## Keywords

- Gradient descent
- Low rank
- Manifold optimization
- Matrix completion
- Phase transition
- Spectral methods

## ASJC Scopus subject areas

- Information Systems
- Computer Science Applications
- Library and Information Sciences