Binary Matrix Completion

• Activity Number: 106
• Type: Invited
• Date/Time: Monday, August 5, 2013 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Yaniv Plan*+ and Mark Davenport and Mary Wootters and Ewout van den Berg
• Companies: University of Michigan and Georgia Institute of Technology and University of Michigan and Stanford
• Keywords: matrix completion ; logistic regression ; maximum likelihood ; convex optimization

Abstract

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.