Benjamin Recht

Center for the Mathematics of Information

California Institute of Technology

 

 

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.

 

Bio:

Benjamin Recht is a senior postdoctoral fellow at Center for the Mathematics of Information---a multidisciplinary research center established to promote information science and technology at Caltech. 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. Benjamin received his B.S. with honors in Mathematics from the University of Chicago in 2000, and received a M.S. in 2002 and PhD in 2006 from the MIT Media Laboratory.

11:00 am - 12:00 pm

Wu & Chen Auditorium

101 Levine Hall