INTERDISCIPLINARY STOCHASTIC PROCESSES COLLOQUIUM Tuesday February 21, room 60 Evans, 4.10 - 5.00pm TITLE: Compressing and binning using sparse random graphs SPEAKER: Martin Wainwright, Departments of Statistics and EECS, UC Berkeley ABSTRACT: Two key problems in information theory are reliable communication over a noisy channel (the "channel coding problem"), and compressing data subject to a distortion constraint (the "lossy source coding problem"). The pioneering work of Shannon characterizes the fundamental limits, but its non-constructive nature leaves open the task of devising explicit constructions to saturate the bounds. Over the past decade, remarkable progress has been made using error-correcting codes based on sparse random graphs, particularly turbo and low-density parity check (LDPC) codes, to solve the channel-coding problem. For lossy compression, in contrast, progress thus far has been relatively limited. In this talk, we begin by motivating and describing the use of sparse graphical codes in communication problems. We then turn to analysis of random ensembles of low-density generator matrix (LDGM) codes for problems of lossy data compression. Using moment methods, we provide bounds on their rate-distortion performance, which (in the terminology of satisfiability problems) amount to bounds on the average optimal value of random MAX k-XORSAT problems. These bounds show that LDGM ensembles saturate the Shannon bound if the degree k is suitably scaled with blocklength. We then introduce and analyze the performance of compound ensembles of LDGM and LDPC codes, and prove that they can saturate the Shannon rate-distortion bound with finite degrees (i.e., independent of blocklength). Based on joint work with Emin Martinian, MERL.