On Exact and -Rényi Common Informations
arXiv:1810.00295
Abstract
Recently, two extensions of Wyner's common information\textemdash exact and Rényi common informations\textemdash were introduced respectively by Kumar, Li, and El Gamal (KLE), and the present authors. The class of common information problems involves determining the minimum rate of the common input to two independent processors needed to exactly or approximately generate a target joint distribution. For the exact common information problem, exact generation of the target distribution is required, while for Wyner's and -Rényi common informations, the relative entropy and Rényi divergence with order were respectively used to quantify the discrepancy between the synthesized and target distributions. The exact common information is larger than or equal to Wyner's common information. However, it was hitherto unknown whether the former is strictly larger than the latter for some joint distributions. In this paper, we first establish the equivalence between the exact and -Rényi common informations, and then provide single-letter upper and lower bounds for these two quantities. For doubly symmetric binary sources, we show that the upper and lower bounds coincide, which implies that for such sources, the exact and -Rényi common informations are completely characterized. Interestingly, we observe that for such sources, these two common informations are strictly larger than Wyner's. This answers an open problem posed by KLE. Furthermore, we extend Wyner's, -Rényi, and exact common informations to sources with countably infinite or continuous alphabets, including Gaussian sources.
arXiv comment42 pages
References in corpus (11)
- Rényi Divergence and Kullback-Leibler Divergence
- General state space Markov chains and MCMC algorithms
- Coordination Capacity
- Distributed Channel Synthesis
- Quantum Reverse Shannon Theorem
- Compression of sources of probability distributions and density operators
- Heuristics for Exact Nonnegative Matrix Factorization
- Empirical processes, typical sequences and coordinated actions in standard Borel spaces
- Wyner's Common Information: Generalizations and A New Lossy Source Coding Interpretation
- Generalized Common Informations: Measuring Commonness by the Conditional Maximal Correlation
- Corrections to "Wyner's Common Information under Rényi Divergence Measures"