TY - GEN

T1 - Matrix completion from a few entries

AU - Keshavan, Raghunandan H.

AU - Oh, Sewoong

AU - Montanari, Andrea

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70449469955&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449469955&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2009.5205567

DO - 10.1109/ISIT.2009.5205567

M3 - Conference contribution

AN - SCOPUS:70449469955

SN - 9781424443130

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 324

EP - 328

BT - 2009 IEEE International Symposium on Information Theory, ISIT 2009

T2 - 2009 IEEE International Symposium on Information Theory, ISIT 2009

Y2 - 28 June 2009 through 3 July 2009

ER -