One-bit matrix completion

Start: 05/08/2013 - 1:15pm
End  : 05/08/2013 - 2:15pm

Applied Math Seminar

Mark A. Davenport (School of Electrical and Computer Engineering, Georgia Institute of Technology)


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.