Computer Science Colloquium
Pulling Rank: Inference from Incomplete Data
Benjamin Recht, California Institute of Technology
March 25, 2009
Warren Weaver Hall, 1302
251 Mercer Street
New York, NY 10012-1110
Spring 2009 Colloquia Calendar
overton AT cs.nyu.edu
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.