Learning Low Rank Matrices from O(n) Entries

2008/12/14 by Raghunandan H. Keshavan, Andrea Montanari, Keshavan, Raghunandan H. +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.0812.2599

8 pages, 11 figures, Forty-sixth Allerton Conference on Communication, Control and Computing, invited paper

arxiv created 2008/12/14 · arxiv updated 2009/12/01

Abstract

How many random entries of an n by m, rank r matrix are necessary to reconstruct the matrix within an accuracy d? We address this question in the case of a random matrix with bounded rank, whereby the observed entries are chosen uniformly at random. We prove that, for any d>0, C(r,d)n observations are sufficient. Finally we discuss the question of reconstructing the matrix efficiently, and demonstrate through extensive simulations that this task can be accomplished in nPoly(log n) operations, for small rank.

Related

• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Accurate low-rank matrix recovery from a small number of linear measurements
• A Simpler Approach to Matrix Completion
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Matrix Completion from Non-Uniformly Sampled Entries