TY - JOUR
T1 - Matrix completion from a few entries
AU - Keshavan, Raghunandan H.
AU - Montanari, Andrea
AU - Oh, Sewoong
N1 - Funding Information:
Manuscript received March 18, 2009; revised November 12, 2009. Current version published May 19, 2010. This work was supported in part by a Terman fellowship and in part by an NSF CAREER award (CCF-0743978). The material in this paper was presented in part at ISIT, Seoul, Korea, July 2009. R. H. Keshavan and S. Oh are with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA (e-mail: raghuram@stanford. edu; [email protected]). A. Montanari is with the Department of Electrical Engineering and the Departments of Statistics, Stanford University, Stanford, CA 94305 USA (e-mail: [email protected]). Communicated by J. Romberg, Associate Editor for Signal Processing. Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2010.2046205 1Indeed, in 2006, NETFLIX made public such a dataset with , and and challenged the research community to predict the missing ratings with root mean square error below 0.8563 [29].
PY - 2010/6
Y1 - 2010/6
N2 - 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/n3 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.
AB - 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/n3 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.
KW - Gradient descent
KW - Low rank
KW - Manifold optimization
KW - Matrix completion
KW - Phase transition
KW - Spectral methods
UR - http://www.scopus.com/inward/record.url?scp=77956897560&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77956897560&partnerID=8YFLogxK
U2 - 10.1109/TIT.2010.2046205
DO - 10.1109/TIT.2010.2046205
M3 - Article
AN - SCOPUS:77956897560
SN - 0018-9448
VL - 56
SP - 2980
EP - 2998
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 6
M1 - 2046205
ER -