One-bit matrix completion

The problem of recovering a matrix from an incomplete sampling of its entries"”also known as matrix completion"”arises in a wide variety of practical situations. In many of these settings, however, the observations are not only incomplete, but also highly quantized, often even to a single bit. Thus we ask, "Given just the signs of a subset of noisy entries of an unknown matrix, can the unknown matrix be reconstructed?" We show that under an approximate low-rank assumption, nuclear-norm constrained maximum-likelihood estimation gives a nearly minimax solution, and that in some regimes almost no information is lost by quantizing to a single bit.

Yaniv Plan received his B.A. from the University of California, Berkeley in 2004 where he double majored in Applied Mathematics and Physics. He earned his Ph.D. in Applied and Computational Mathematics at Caltech in 2011 where he received the W.P. Carey and Co. Inc. prize for outstanding doctoral dissertation. He was also a Visiting Mathematical Researcher at Stanford in 2010-2011. He currently holds a Hildebrandt Assistant Professorship in Mathematics at the University of Michigan in conjunction with an NSF Postdoctoral Fellowship. His main areas of interest applied probability, theoretical statistics, compressive sensing, sparse approximation, low-rank matrix recovery, and non-asymptotic random matrix theory