# Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. — known problem?

Consider the following problem. Let $X$ and $Y$ be discrete random variables. The goal is to find a random variable $Z$ such that, informally, $I(Z;X)$ is high and $I(Z;Y)$ is low.

More precisely, either: $~\max_Z I(Z;X) ~\text{s.t.}~ I(Z;Y) \le c~$ or $~\min_Z I(Z;Y) ~\text{s.t.}~ I(Z;X) \ge c~$ (for some constant $c$).

This seems like a very natural, fundamental (if toy?) problem, so surely something is known about it. (I know that for $X,Y$ both with finite support, (large) linear programs can be written to solve for such $Z$, but I imagine there's a neater way.) Any pointers would be appreciated.

Thanks!

• How are the distributions of $X,Y$ represented? If the support of $X,Y$ is small enough that you can write down the distribution of $X,Y$ explicitly (by providing the probability of each of their possible values), then it seems like linear programming should be a fine solution and you won't need anything new. On the other hand, if their support is so large that LP is infeasible (e.g., their support is exponentially large), then you're going to need some other way of representing their distribution. Did you have something particular in mind? – D.W. Jul 29 '13 at 20:53
• Note that this is a duplicate of mathoverflow.net/questions/138043/… – minar Jul 31 '13 at 15:43
• Asking simultaneously on two StackExchange sites is considered bad form. Please don't do that. Please select one to keep, and click the "flag" button on the other to ask the moderators to close it. – D.W. Aug 2 '13 at 5:29

Roughly, $Y$ represents the rows of a joint distribution and $X$ represents the columns. The random variable $Z$ then represents a distribution over the rows ($Y$) that is highly compressed (because $I(Z;Y)$ is small) but represents the joint distribution well (because $I(Z;X)$ is large).
• Thanks, @suresh-venkat, just what I was looking for. I (et al.) believe it can be solved by LP, after a structure theorem limiting us wlog to certain kinds of $p(Z|X,Y)$. I take it there are not optimal algorithms known for IB then? Slonin's 2002 thesis states the problem is NP-hard "in general", citing The complexity of the generalized Lloyd-Max problem (Garey et al., 1982). I haven't been able to look at this paper yet, but it sounds like IB may only be known to be a special case of a hard problem. (Unless our LP argument is flawed!) – Matt Aug 1 '13 at 1:26
• Just to clarify a couple of (ultimately somewhat deflating) things about the LP and $p(Z|X,Y)$: we can write an honest-to-goodness LP (vars of the form $p(z|X=x,Y=y)$, all the logs ending up in the constants) to find the best $p(Z|X,Y)$ with a given structure, after having proven that there must exist an optimal $p(Z|X,Y)$ with that structure. Unfortunately, and perhaps this makes the preceding suddenly way less suspicious, the LP is exponentially large (in support of $p(X,Y)$). – Matt Aug 1 '13 at 21:42