  We propose an approach to lossy source coding, utilizing ideas from Gibbs
sampling, simulated annealing, and Markov Chain Monte Carlo (MCMC). 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
i-th 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 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). We show that the proposed
algorithms achieve optimum rate-distortion performance in the limits of large
number of iterations, and sequence length, when employed on any stationary
ergodic source. Experimentation shows promising initial results. 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).
