Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
arXiv:0710.0192
Abstract
We propose a new algorithm for binary quantization based on the Belief Propagation algorithm with decimation over factor graphs of Low Density Generator Matrix (LDGM) codes. This algorithm, which we call Bias Propagation (BiP), can be considered as a special case of the Survey Propagation algorithm proposed for binary quantization by Wainwright et al. [8]. It achieves the same near-optimal rate-distortion performance with a substantially simpler framework and 10-100 times faster implementation. We thus challenge the widespread belief that binary quantization based on sparse linear codes cannot be solved by simple Belief Propagation algorithms. Finally, we give examples of suitably irregular LDGM codes that work with the BiP algorithm and show their performance.
Forty-Fifth Annual Allerton Conference on Communication, Control, and Computing, 2007, 10 pages, 6 figures
References in corpus (3)
Cited by in corpus (13)
- Polar Codes are Optimal for Lossy Source Coding
- Design and Analysis of LDGM-Based Codes for MSE Quantization
- Learned Decimation for Neural Belief Propagation Decoders
- Successive Wyner-Ziv Coding for the Binary CEO Problem under Logarithmic Loss
- Lower Bounds on the Rate-Distortion Function of Individual LDGM Codes
- On Superposition Coding for the Wyner-Ziv Problem
- Approaching the Rate-Distortion Limit with Spatial Coupling, Belief propagation and Decimation
- Blahut-Arimoto Algorithm and Code Design for Action-Dependent Source Coding Problems
- Lossy Source Compression of Non-Uniform Binary Sources Using GQ-LDGM Codes
- Graph-based Code Design for Quadratic-Gaussian Wyner-Ziv Problem with Arbitrary Side Information
- Successive Wyner-Ziv Coding for the Binary CEO Problem under Log-Loss
- Analytical Framework of LDGM-based Iterative Quantization with Decimation
- Lower Bounds on the Rate-Distortion Function of LDGM Codes