Analytical Framework of LDGM-based Iterative Quantization with Decimation

Abstract

While iterative quantizers based on low-density generator-matrix (LDGM) codes have been shown to be able to achieve near-ideal distortion performance with comparatively moderate block length and computational complexity requirements, their analysis remains difficult due to the presence of decimation steps. In this paper, considering the use of LDGM-based quantizers in a class of symmetric source coding problems, with the alphabet being either binary or non-binary, it is proved rigorously that, as long as the degree distribution satisfies certain conditions that can be evaluated with density evolution (DE), the belief propagation (BP) marginals used in the decimation step have vanishing mean-square error compared to the exact marginals when the block length and iteration count goes to infinity, which potentially allows near-ideal distortion performances to be achieved. This provides a sound theoretical basis for the degree distribution optimization methods previously proposed in the literature and already found to be effective in practice.

Submitted to IEEE Transactions on Information Theory

References in corpus (7)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
• Analysis of LDGM and compound codes for lossy compression and binning
• Low-density graph codes that are optimal for source/channel coding and binning
• Polar Codes are Optimal for Lossy Source Coding
• Design and Analysis of LDGM-Based Codes for MSE Quantization
• Average Entropy Functions