Return to Colloquia & Seminar listing
One-bit matrix completionPDE and Applied Math Seminar
|Speaker: ||Yaniv Plan, University of Michigan|
|Location: ||1147 MSB|
|Start time: ||Mon, Nov 19 2012, 3:10PM|
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.