I will introduce a model for using quality information to perform lossy compression and discuss practical implementations based on belief propagation. Specifically, consider a source signal, X, and some quality side information, Q. For example, Q could represent reliabilities for noisy measurements, differing relative importance due to context, or perceptual effects in the human audio-visual system.
When an encoder describes X to a decoder, the goal is to convey important components (as indicated by Q) more accurately. If both encoder and decoder know Q, the obvious solution is to spend more bits on describing important parts of X. But what if only the encoder or only the decoder knows Q? Can the quality information still be useful, or is there a fundamental penalty due to lack of shared information?
A surprising answer from information theory is that knowing Q at the decoder is often useless while knowing Q at the encoder is often as good as full knowledge of Q. Furthermore, by using a new type of belief propagation encoding rule, it is possible to build practical systems that achieve the full gains promised by the theory while requiring only linear computational complexity.
This is joint work with Gregory Wornell and Ram Zamir.