Back to Search
Start Over
Minimum-Entropy Couplings and Their Applications.
- Source :
- IEEE Transactions on Information Theory; Jun2019, Vol. 65 Issue 6, p3436-3451, 16p
- Publication Year :
- 2019
-
Abstract
- Given two discrete random variables $X$ and $Y$ , with probability distributions $p=(p_{1}, \ldots , p_{n})$ and $q=(q_{1}, \ldots , q_{m})$ , respectively, let us denote by ${\mathcal{ C}}(p, q)$ the set of all couplings of $p$ and $q$ , that is, the set of all bivariate probability distributions that have $p$ and $q$ as marginals. In this paper, we study the problem of finding a joint probability distribution in ${\mathcal{ C}}(p, q)$ of minimum entropy (equivalently, a coupling that maximizes the mutual information between $X$ and $Y$), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in ${\mathcal{ C}}(p, q)$ with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum-entropy joint distribution of arbitrary $k\geq {2}$ discrete random variables $X_{1}, \ldots , X_{k}$ , consistent with the known $k$ marginal distributions of the individual random variables $X_{1}, \ldots , X_{k}$. In this case, our algorithm has an additive gap of at most $\log k$ from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 65
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 136543523
- Full Text :
- https://doi.org/10.1109/TIT.2019.2894519