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.
An appropriate choice of the energy function leads to an algorithm whose complexity, in 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 is universal: for any stationary ergodic source, it achieves the optimal rate distortion performance in the limits of large number of iterations, and sequence length. These theoretical findings are confirmed by initial experimentation showing near Shannon limit performance in practice.
Our approach scales naturally to other lossy compression scenarios, such as lossy compression with decoder side information (a.k.a. the Wyner-Ziv problem). The resulting schemes enjoy algorithmic and universality properties that are analogous to those of their vanilla counterpart.
Time permitting, we will examine the implications and application of our approach to the denoising problem: Employing our lossy compressor on the noisy data, with appropriately chosen distortion measure and level, followed by a simple de-randomization operation, results in a practical and provably universal denoiser. The resulting scheme compares favorably with other MCMC-based schemes, and with the more recently introduced Discrete Universal Denoiser (DUDE).
Based on joint work with Shirin Jalali (Stanford University).
BiographyTsachy Weissman received the B.Sc. (Summa Cum Laude) and Ph.D. degrees, both in electrical engineering from the Technion, Israel Institute of Technology, in 1997 and 2001, respectively.
During the fall semester of 2001-2002 he was with the Technion Electrical Engineering Department. During 2002-2003 he was visiting the Statistics Department at Stanford, and was with the information theory research group at Hewlett-Packard Laboratories, to which he is now a consultant. He has been on the Stanford faculty since 2003, where he is Assistant Professor of Electrical Engineering and Robert N. Noyce Scholar of the School of Engineering.
Tsachy's research interests span information theory and its applications, and statistical signal processing. Among his awards are the Clore Foundation scholarship, the Intel Prize, the Viterbi scholarship, the Rothschild foundation scholarship for postdoctoral studies, and the NSF CAREER. He is a co-recipient of the 2006 joint IT/COM societies paper award.