Computational Limits for Matrix Completion

Moritz Hardt, Raghu Meka, Prasad Raghavendra +1

Matrix Completion is the problem of recovering an unknown real-valued low-rank matrix from a subsample of its entries. Important recent results show that the problem can be solved…