WNCG Seminar Series with Mary Wootters

In the matrix completion problem, one sees a few entries of an (approximately) low-rank matrix and hopes to (approximately) recover the entire matrix.  This problem has gotten a lot of attention recently, partly due to its applicability to recommender systems.  It is known that, by solving a convex program, the original matrix can be recovered 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, Dr. Wootters gives a fast algorithm for matrix completion---with runtime and sample complexity linear in n---which incurs only a logarithmic dependence on the condition number.  Dr. Wootters' algorithm is based on an extension of Alternating Minimization.  This is joint work with Moritz Hardt.