Fast Matrix Completion Without the Condition Number

We give the first algorithm for Matrix Completion that achieves running time and sample complexity that is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, a