[Colloquium] TTI-C Colloquium: Ben Recht, University of Wisconsin- Madison

[Julia MacGlashan]

*Reminder*

When:             *Monday, Oct 26 @ 1:00pm*

Where:           * TTI-C Conference Room #526*, 6045 S Kenwood Ave

Who:               *Ben Recht*, University of Wisconsin-Madison

Title:          *      A simpler approach to matrix completion*


Matrix completion—where one seeks to recover a low rank matrix from a given
subset of its entries—is a recurring problem in collaborative filtering,
dimensionality reduction, and multi-class learning.  While the general
problem of finding the lowest rank matrix satisfying a set of equality
constraints is NP-hard, in this talk I will discuss very general settings
under which one can perfectly recover all of the missing entries of a
low-rank matrix by solving a convex optimization problem.  I will show that
this convex programming heuristic can reconstruct most n x n matrices of
rank r from most collections of entries, provided that the number of entries
exceeds C n r log^2 n for some small, positive numerical constant C. These
results improve on prior work by Candes and Recht, Candes and Tao, and
Keshavan, Montanari, and Oh and build upon geometric ideas from the
literature on "Compressed Sensing." The proof of bound on the number entries
is short, self-contained, and uses very elementary analysis based on recent
developments in quantum information theory. I will conclude by discussing
how these results illustrate a general program for perfectly reconstructing
geometric objects from very limited information.

Bio: Benjamin Recht is an Assistant Professor of Computer Sciences at the
University of Wisconsin-Madison. His research focuses on scalable
computational tools based on convex optimization and randomized algorithms
for large-scale data analysis, system identification, machine learning, and
mathematical physiology. He was previously senior postdoctoral fellow at
Center for the Mathematics of Information--a multidisciplinary research
center established to promote information science and technology at Caltech.
Recht received his B.S. with honors in Mathematics from the University of
Chicago in 2000, and received a M.S. in 2002 and Ph.D. in 2006 from the MIT
Media Laboratory.

Contact:          Nati Srebro, TTI-C       nati at tti-c.org
834-7493
Speaker Schedule: http://www.tti-c.org/colloquium.php
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20091026/a2a5e088/attachment.htm