- Series
- Stochastics Seminar
- Time
- Thursday, February 7, 2013 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skyles 006
- Speaker
- Mark Davenport – Georgia Institute of Technology
- Organizer
- Karim Lounici
In this talk I will describe a theory of matrix completion for the extreme
case of noisy 1-bit observations. In this setting, 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 address is whether or not it is possible to obtain an
accurate estimate of M from this data. In general this would seem
impossible, but I will show that the maximum likelihood estimate under a
suitable constraint returns an accurate estimate of M when $\|M\|_{\infty}
\le \alpha$ and $\rank(M) \le r$. If the log-likelihood is a concave
function (e.g., the logistic or probit observation models), then we can
obtain this maximum likelihood estimate by optimizing a convex program. I
will also provide lower bounds showing that this estimate is near-optimal
and illustrate the potential of this method with some preliminary numerical
simulations.