[Colloquium] REMINDER: Talk by Benjamin Recht Today

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Thursday, February 19, 2009
Time: 3:00 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Benjamin Recht

From:		CalTech

Website:		http://www.ist.caltech.edu/%7Ebrecht/

Title:     Pulling Rank: Inference from Incomplete Data

Abstract:   How can we infer answers from a survey that is only
partially filled out? Suppose we ask a large collection of individuals
a series of questions. We collect some data but, unfortunately, many
questions are left unanswered. Is it possible for us to make an
educated guess about what the missing answers should be? How can we
make such a guess? In general, with no additional assumptions, this is
impossible. However, if we assume that we can arrange all of the
answers into a low rank matrix, there is often a unique assignment for
the missing entries.
The rank of a matrix is equal to the dimension of the span of its
columns (or rows). Matrix rank is often an efficient way to describe
system order, complexity, or dimensionality. Moreover, matrices of
very low rank can be uniquely specified by very few parameters.
Consequently, rank minimization---finding the minimum rank matrix that
agrees with some partial measurements---is a recurring problem in
engineering and computer science. Unfortunately, although specific
instances can often be solved with specialized algorithms, the general
rank minimization problem is NP-hard.

In this talk, I will construct a convex relaxation of the rank
minimization problem that provably produces the minimum rank solution
in a variety of practical scenarios. In particular, the relaxation can
perfectly recover most low-rank matrices from a small partial subset
of entries. I will subsequently outline practical implementations of
this heuristic that can be efficiently applied to large-scale problems
with guaranteed success. The techniques used in this analysis have
strong parallels in the “Compressed Sensing” framework where one seeks
to find the vector of smallest cardinality in an affine set. I will
discuss how rank minimization generalizes this pre-existing concept
and outline a dictionary relating concepts from cardinality
minimization to those of rank minimization. I will then discuss how to
generalize these techniques to efficiently recover structured objects
arising in dynamical systems, function fitting, and dimensionality
reduction from very limited information.


Refreshments will be served following the talk in RY 255 at 4:00
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090219/4a94a983/attachment.htm