Colloquium Details
Pulling Rank: Inference from Incomplete Data
Speaker: Benjamin Recht, California Institute of Technology
Location: Warren Weaver Hall 1302
Date: March 25, 2009, 11:30 a.m.
Host: Michael Overton
Synopsis:
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.
Notes:
In-person attendance only available to those with active NYU ID cards.