Gradient Decoding Revisited

Modern coding applications, including dirty paper coding and information hiding, hinge critically on a classical ´general decoding problem,´ known to be NP hard. Various attempts to find good solutions at reasonable complexity can be traced throughout the decades, most recently with attempts to achieve the rate-distortion bound in code word quantization. Here we take a step back to examine two computationally simple procedures in this direction: gradient decoding and a simple yet surprisingly effective variant on belief propagation that we dub truthiness propagation.