Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 56, Issue 6, Pages 2980-2998Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2010.2046205
Keywords
Gradient descent; low rank; manifold optimization; matrix completion; phase transition; spectral methods
Funding
- Terman fellowship
- NSF [CCF-0743978]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [743978] Funding Source: National Science Foundation
Ask authors/readers for more resources
Let be an M be ab n alpha xn 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 vertical bar E vertical bar = O(r n) observed entries with relative root mean square error RMSE <= C(alpha) (nr/vertical bar E vertical bar)(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 vertical bar E vertical bar = 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 Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(vertical bar E vertical bar 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-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available