TITLE: One-bit Matrix Completion

SPEAKER:  Mark Davenport

ABSTRACT:

In this talk I will describe a theory of matrix completion for the extreme case of noisy 1-bit observations. Instead of observing a subset of the real-valued entries of a matrix M, we obtain a small number of binary (1-bit) measurements generated according to a probability distribution determined by the real-valued entries of M. The central question I will discuss is whether or not it is possible to obtain an accurate estimate of M from this data. In general this would seem impossible, but we show that the maximum likelihood estimate under a suitable constraint returns an accurate estimate of M under certain natural conditions. If the log-likelihood is a concave function (e.g., the logistic or probit observation models), then we can obtain this estimate by optimizing a convex program.

Mark's email is mdav@gatech.edu.