Information Spectrum Converse for Minimum Entropy Couplings and Functional Representations
share
Given two jointly distributed random variables (X,Y), a functional representation of X is a random variable Z independent of Y, and a deterministic function g(·, ·) such that X=g(Y,Z). The problem of finding a minimum entropy functional representation is known to be equivalent to the problem of finding a minimum entropy coupling where, given a collection of probability distributions P_1, …, P_m, the goal is to find a coupling X_1, …, X_m (X_i ∼ P_i) with the smallest entropy H_α(X_1, …, X_m). This paper presents a new information spectrum converse, and applies it to obtain direct lower bounds on minimum entropy in both problems. The new results improve on all known lower bounds, including previous lower bounds based on the concept of majorization. In particular, the presented proofs leverage both - the information spectrum and the majorization - perspectives on minimum entropy couplings and functional representations.
READ FULL TEXT