A Caltech Library Service

Block and Sliding-Block Lossy Compression via MCMC

Jalali, Shirin and Weissman, Tsachy (2012) Block and Sliding-Block Lossy Compression via MCMC. IEEE Transactions on Communications, 60 (8). pp. 2187-2198. ISSN 0090-6778. doi:10.1109/TCOMM.2012.061412.110194.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We propose an approach to lossy compression of finite-alphabet sources that utilizes Markov chain Monte Carlo (MCMC) and simulated annealing methods. The idea is to define an energy function over the space of reconstruction sequences. The energy of a candidate reconstruction sequence is defined such that it incorporates its distortion relative to the source sequence, its compressibility, and the point sought on the rate-distortion curve. The proposed algorithm samples from the Boltzmann distribution associated with this energy function using the "heat-bath" algorithm. The complexity of each iteration is independent of the sequence length and is only linearly dependent on a certain context parameter, which grows sub-logarithmically with the sequence length. We show that the proposed algorithm achieves optimum rate-distortion performance in the limits of large number of iterations, and sequence length, when employed on any stationary ergodic source. Inspired by the proposed block-coding algorithm, we also propose an algorithm for constructing sliding-block (SB) codes using similar ideas.

Item Type:Article
Related URLs:
Additional Information:© 2012 IEEE. Paper approved by Z. Xiong, the Editor for Distributed Coding and Processing of the IEEE Communications Society. Manuscript received April 10, 2011; revised September 26, 2011 and January 19, 2012.
Subject Keywords:Rate-distortion coding; universal lossy compression; Markov chain Monte Carlo; Gibbs sampler; simulated annealing
Issue or Number:8
Record Number:CaltechAUTHORS:20121106-102959153
Persistent URL:
Official Citation:Jalali, Shirin; Weissman, Tsachy; , "Block and Sliding-Block Lossy Compression via MCMC," Communications, IEEE Transactions on , vol.60, no.8, pp.2187-2198, August 2012 doi: 10.1109/TCOMM.2012.061412.110194 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:35301
Deposited By: Tony Diaz
Deposited On:06 Nov 2012 22:53
Last Modified:09 Nov 2021 23:14

Repository Staff Only: item control page