WNCG Seminar Series with Mary Wootters

Seminar
Friday, December 05, 2014
11:00am - 12:00pm
UTA 7.532

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.

Speaker

Postdoctoral Fellow
Carnegie Mellon University
Mary Wootters recently defended her PhD thesis in the math department at the University of Michigan, under the supervision of Martin Strauss.  Before coming to Michigan, she received a B.A. in math and computer science from Swarthmore College.  

From July-August, 2014, Wootters interned at the IBM Almaden theory group. Starting in September 2014, Wootters will be a NSF postdoctoral fellow in the CS department at Carnegie Mellon University, working with Venkat Guruswami. Her interests lie mostly in applied probability, with applications including randomized algorithms, compressed sensing, matrix completion, coding theory, and group testing.  I dabble in quantum information theory and complexity theory.