Information Theory Seminar

TITLE: Rate Distortion via Markov Chain Monte Carlo

SPEAKER: Tsachy Weissman (Stanford University and Technion)

DATE: 2:00 - 3:00 PM, Wednesday, August 13, 2008

LOCATION: Tioga, 3U

ABSTRACT:
I will describe a new approach to lossy source coding. The idea is to sample a reconstruction sequence from a Boltzmann distribution associated with an energy function that incorporates the distortion between the source and reconstruction, the compressibility of the reconstruction, and the point sought on the rate-distortion curve. To sample from this distribution, we use a 'heat bath algorithm': Starting from an initial candidate reconstruction (say the original source sequence), at every iteration, an index i is chosen and the ith sequence component is replaced by drawing from the conditional probability distribution for that component given all the rest. At the end of this process, the encoder losslessly conveys the reconstruction to the decoder using universal lossless compression.

The complexity of each iteration is independent of the sequence length and only linearly dependent on a certain context parameter (which grows sub-logarithmically with the sequence length). The algorithm achieves optimum rate distortion performance in the limits of large number of iterations, and sequence length, when employed on any stationary ergodic source. These theoretical findings are confirmed by initial experimentation showing near Shannon limit performance in practice.

Employing our lossy compressors on noisy data, with appropriately chosen distortion measure and level, followed by a simple de-randomization operation, results in a family of denoisers that compares favorably (both theoretically and in practice) with other MCMC-based schemes, and with the Discrete Universal Denoiser (DUDE).

This research, which is joint with Shirin Jalali, was funded by and performed in part at HP Labs Palo Alto.

BIOGRAPHY:
Tsachy Weissman graduated with a PhD in electrical engineering from the Technion in 2001. He has held a postdoctoral appointment with Hewlett-Packard Laboratories at Palo Alto. He joined the faculty of the Electrical Engineering department at Stanford University in 2003. He has been also with the department of Electrical Engineering at the Technion since the summer of 2007.

Tsachy's research interests span information theory and its applications, and statistical signal processing. His papers have focused mostly on data compression, prediction, denoising, communications, and learning. He is also inventor or co-inventor of several patents in these areas. In addition to his academic activities, Tsachy is a consultant to several high-tech companies.

Among other prizes, he was awarded the Clore Foundation scholarship, the Rothschild Foundation scholarship for postdoctoral studies, the NSF CAREER award, and a Horev fellowship. He was a Robert N. Noyce Faculty Scholar of the School of Engineering at Stanford University, and is a recipient of the 2006 IEEE joint Information Theory/Communications societies best paper award.