FoCM 2014 conference
Workshop A2 - Computational Harmonic Analysis, Image and Signal Processing
December 11, 18:30 ~ 18:55 - Room C21
Matrix recovery from coarse observations
Mark Davenport
Georgia Institute of Technology, USA - mdav@gatech.edu
In this talk I will describe a theory and techniques for solving matrix completion and similar problems when given extremely coarse (e.g., 1-bit) observations. As an example, instead of observing a subset of the real-valued entries of a matrix M, we might 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 discuss is whether or not it is possible to obtain an accurate estimates of M from data of this form. 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 under certain natural conditions. I will conclude by discussing several extensions and applications of these techniques to similar problems.
Joint work with Yaniv Plan (University of British Columbia), Ewout van den Berg (IBM Watson) and Mary Wootters (Carnegie Mellon University).