Thomas Courtade - Lossy Compression for BigData: A First Step

Thursday, July 26, 2012
2:00 pm - 3:00 pm EST/EDT
Felix Haas Hall, Rm. 111
Purdue University

Thomas Courtade

Assistant Professor
Department of Electrical Engineering and Computer Science
UC, Berkeley

Two key challenges in fitting BigData problems into a lossy compression framework are (i) the selection of an appropriate distortion measure, and (ii) characterizing the performance of distributed systems.  Inspired by real systems, like Google, which return a list of likely data entries indexed by likelihood, we study the "logarithmic loss" distortion function in a multiterminal setting, thus addressing both challenges.  In particular, we characterize the rate-distortion region for two (generally open) multiterminal source coding problems when distortion is measured under logarithmic loss.  In addition to the main results, I'll discuss applications to machine learning, estimation, and combinatorics.