Computer Science – Information Theory
Scientific paper
2008-08-29
Computer Science
Information Theory
35 pages, 16 figures, Submitted to IEEE Transactions on Information Theory
Scientific paper
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).
Jalali Shirin
Weissman Tsachy
No associations
LandOfFree
Rate-Distortion via Markov Chain Monte Carlo does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rate-Distortion via Markov Chain Monte Carlo, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate-Distortion via Markov Chain Monte Carlo will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-544559