TR2005-125

Low Density Codes Achieve the Rate-Distortion Bound


    •  Emin Martinian, Martin Wainwright, "Low Density Codes Achieve the Rate-Distortion Bound", Tech. Rep. TR2005-125, Mitsubishi Electric Research Laboratories, Cambridge, MA, May 2006.
      BibTeX TR2005-125 PDF
      • @techreport{MERL_TR2005-125,
      • author = {Emin Martinian, Martin Wainwright},
      • title = {Low Density Codes Achieve the Rate-Distortion Bound},
      • institution = {MERL - Mitsubishi Electric Research Laboratories},
      • address = {Cambridge, MA 02139},
      • number = {TR2005-125},
      • month = may,
      • year = 2006,
      • url = {https://www.merl.com/publications/TR2005-125/}
      • }
Abstract:

We propose a new construction for low-density source codes with multiple parameters that can be tuned to optimize the performance of the code. In addition, we introduce a set of analysis techniques for deriving upper bounds for the expected distortion of our construction, as well as more general low-density contructions. We show that (with an optimal encoding algorithm) our codes achieve the rate-distortion bound for a binary symmetric source and Hamming distortion. Our methods also provide rigorous upper bounds on the minimum distortion achievable by previously proposed low-density constructions.