Approximate characterization of the multiple description rate region


A multiple description (MD) source coder generates a set of binary streams or descriptions of a source sequence, each with its own rate constraint. It is important in applications requiring robust communication, as well as in distributed storage systems. For the former case, the transmission medium may deliver some or all of the descriptions to the decoder due to unacceptable congestion or channel failure. The design objective is to give distortion guarantees if only some of the descriptions are delivered. In the latter application, one user may have access to only some of the servers, and the quality of reconstruction will depend on how many and which servers the user can access.

The fundamental problem here is to characterize the tuple of admissible rates and distortions for each subset of descriptions. This problem has been open since the late 1970s and even the K-description Gaussian problem, for K>2, is unresolved. The only complete characterization is for the two-description Gaussian source with quadratic distortion constraints.

We make progress on the MD problem by giving an approximate characterization of the rate-distortion region for the Gaussian quadratic source. Given an arbitrary number of descriptions, we first focus on symmetric distortion constraints problem. 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 descriptions, but independent of the exact distortion constraints. Underlying this result is an exact characterization of a lossless multi-level source coding problem: a lossless counterpart of MD problem. This connection helps by giving a polytopic template for the rate region, helping with both the inner and outer bounds. For the outer bound we introduce a new technique which requires a strategic expansion of the original probability space by more than one random variables. As a consequence of this result, for the symmetric rate case with any number of descriptions, it can be shown that the gap between upper bound and lower bound for the individual description rate is no larger than 0.92 bit.

The result also suggests that a very simple architecture is almost optimal (within approximately 1.5 bit per description) for the Gaussian quadratic case. The architecture is that one can cascade a standard layered (hierarchical) source coder with a lossless multi-level coder. Therefore, underlying this is the understanding of the lossless multi-level source coding problem. A more sophisticated scheme involving multi-layered quantization and binning (a slight generalization of the scheme proposed by Pradhan, Puri and Ramchandran, IT Trans., 2005) can improve this constant in the approximate characterization to the aforementioned 0.92 bit. For the gap is even smaller for smaller number of descriptions, for example, for K=3, the gaps are upper bounded by 0.7296 and 0.3821, respectively.

The symmetric lossless multi-level problem was introduced by Roche and Yeung (IEEE Trans. IT, 1997) and was completely solved by Yeung and Zhang (IEEE Trans. IT, 1999). The problem asks for exact (lossless) reconstruction of a set of sources depending on the available set of descriptions. The reconstruction depends only on the number of successful description and not on the actual subset. Therefore, this problem is closely matched to a symmetric version of the multiple description problem. We formulate the asymmetric multi-level problem, in which the reconstruction depends on the successful subset of descriptions and not just on the cardinality (number of descriptions). We have a complete characterization of the rate region for this problem for the three-description case. Interestingly, this result shows that, unlike the symmetric case, the optimal scheme requires us to strategically partition and combine independent sources. The combination of the specifically chosen parts of the independent sources, or “mixing” of them, is very much like “network coding”. Using this result we also have an approximate characterization of the entire rate region for the three-description Gaussian multiple description problem, where like the symmetric couterpart, we show that the entire rate region can be sandwiched between two polytopes with matching hyperplanes, between which the gap can be upper bounded by constant independent of the exact distortion constraints.

Papers

  1. Download: asymmd.pdf on Arxiv 
    Abstract:
    This paper introduces the asymmetric multi-level lossless data compression problem and gives a complete characterization for the three-description version. It then uses insights from this characterization to provide an approximate characterization for the 3-description asymmetric multiple description problem.
  2. Abstract:
    Approximately solves symmetric Gaussian multiple description problem to within a bit, by sandwiching the MD rate region between two polytopes separated by at most a fraction of a bit.
  3. C. Tian, S. Mohajer, and S N. Diggavi, "Approximating the Gaussian multiple description rate region under symmetric distortion constraints," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1413-1417.
  4. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1992-1996.
  5. C. Tian, S. Mohajer, and S. N. Diggavi, "On the symmetric Gaussian multiple description rate-distortion function," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 412-421.
  6. S. Mohajer, C. Tian, and S. N. Diggavi, "Asymmetric Multilevel Diversity Coding," in Proc. IEEE Data Compression Conference (DCC), Snowbird, Utah, 2008, pp. 402-411.
  7. C. Tian, S. Mohajer, and S. N. Diggavi, "On the Gaussian $K$-description problem under symmetric distortion constraints," in Proc. Information Theory and Applications Workshop, UCSD, San Diego, California, 2008, pp. 401-406.