Minimum-Entropy Couplings and Their Applications

DOI10.1109/TIT.2019.2894519MaRDI QIDQ5224007zbMATH OpenOpenAlexWikidataFDO

Authors Ferdinando Cicalese, Luisa Gargano, Ugo Vaccaro

Publication date 19 July 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.07530

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Source coding (94A29) Channel models (including quantum) in information and communication theory (94A40)

Abstract: Given two discrete random variables $X$ and $Y,$ with probability distributions $$ and $$, respectively, denote by $$ the set of all couplings of $$ and $$, that is, the set of all bivariate probability distributions that have $$ and $$ as marginals. In this paper, we study the problem of finding a joint probability distribution in $$ of emph{minimum entropy} (equivalently, a coupling that emph{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 $$ 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 $kgeq2$ 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 $logk$ from optimum.} We also discuss several related applications of our findings and {extensions of our results to entropies different from the Shannon entropy.}

Cited in

(7)

• Difference equations related to majorization theorems via Montgomery identity and Green's functions with application to the Shannon entropy
• Efficient optimal Kolmogorov approximation of random variables
• Efficient approximate minimum-Rényi entropy couplings
• Minimal coupling in Koopman-von Neumann theory
• Channel simulation: theory and applications to lossy compression and differential privacy
• Error estimation for approximate solutions to the minimum entropy coupling problem
• Improvements of Slater's inequality and its applications for power means and divergences

This page was built for publication: Minimum-Entropy Couplings and Their Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224007)