Lower Bounds on the Rate-Distortion Function of LDGM Codes
Georgios Alexandros Dimakis, Martin Wainwright and Kannan Ramchandran
National Science Foundation CCF-0545862 and National Science Foundation CCF-0635372
We analyze the performance of low-density generator matrix (LDGM) codes for lossy source coding. We first develop a generic technique for deriving lower bounds on the effective rate-distortion functions of binary linear codes. This result provides a source coding analog of a classical result due to Gallager for channel coding over the binary symmetric channel. We illustrate this method for the ensemble of check-regular low-density generator matrix (LDGM) codes by deriving an explicit lower bound on its rate-distortion performance as a function of the check degree.
- A. G. Dimakis, M. J. Wainwright, and K. Ramchandran, "Lower Bounds on the Rate-Distortion Function of LDGM Codes," Information Theory Workshop (ITW), 2007.