Approximation of the Multiple Description Problem

In this problem a single source sequence is encoded into several streams, each of a certain rate. There are multiple users, each observes a subset of the compressed streams and aims to reconstruct the source within a certain fidelity. The  design object here is to give distortion guarantee depending on the set of available descriptions for each user. The fundamental question in the so-called Multiple Description (MD) source coding problem is to characterize the trade-off between the tuple of admissible rates and users’ distortions.

A multiple description code is important in application requiring robust communication, as well as in distributed storage systems, where each user may have access to only some if the servers. 

This problem was introduced in the late 1970's, and has remained unsolved except for a special case in which K=2, and the source sequence is sampled from a Gaussian distribution.  However, it can be considered as a lossy version of the multi-level diversity coding problem. Given the results obtained for the lossless problem,  we make progress on the MD problem by giving an approximate characterization of the rate-distortion region for the Gaussian source with quadratic distortion. We show that the rate region can be sandwiched between two polytopes with matching hyperplanes, between which the gap can be upper bounded by constants dependent on the number of the descriptions, but not the distortion constraints.  

Approximation of the Multiple Description Problem