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   -

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).

View abstract PDF