Fast matrix completion without the condition number

Abstract: In the matrix completion problem, one sees a few entries of an approximately low-rank matrix and hopes to recover the entire matrix. This problem has gotten a lot of attention recently, partly due to its applicability to recommender systems. When one has a lot of time on one's hands (time at least n^2 for an nxn matrix), it is known how to recover the original matrix with a number of observations that is linear in n. However, for current analyses of faster algorithms (with runtime linear in n), the number of samples additionally depends at least quadratically on the *condition number* of the matrix. In this work, we give a fast algorithm for matrix completion—with runtime and sample complexity linear in n—which incurs only a logarithmic dependence on the condition number. Our algorithm is based on an extension of Alternating Minimization. This is joint work with Moritz Hardt.