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 -