Lower bounds for quantized matrix completion

In this paper we consider the problem of 1-bit matrix completion, where 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 we ask is whether or not it is possible to obtain an accurate estimate of M from this data. In general this would seem impossible, however, it has recently been shown in [1] that under certain assumptions it is possible to recover M by optimizing a simple convex program. In this paper we provide lower bounds showing that these estimates are near-optimal.