Theory Seminar
Women in Computing

Fast matrix completion without the condition number

Mary Wootters

Carnegie Mellon University
Friday, November 21, 2014
10:30am - 11:30am
3941 BBB

Add to Google Calendar

About the Event

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.

Additional Information

Sponsor(s): CSE

Open to: Public