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.


  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Jul 29 '13 at 20:53
  • 2
    $\begingroup$ Note that this is a duplicate of mathoverflow.net/questions/138043/… $\endgroup$ – minar Jul 31 '13 at 15:43
  • $\begingroup$ 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. $\endgroup$ – D.W. Aug 2 '13 at 5:29

In one form, your question is actually a clustering question that is addressed by the information bottleneck method.

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).

It's not clear to me that this can be solved using LPs. the underlying problem is not convex. But there's a simple EM-style alternating optimization scheme that can be used to solve it.

  • $\begingroup$ Thanks, @Suresh, this is just what I was looking for. (My version seems to be a very slight generalization.) I (et al.) believe it can be solved by LP, after a structure theorem limiting wlog us to certain kinds of joint distributions. $\endgroup$ – Matt Aug 1 '13 at 1:13
  • $\begingroup$ 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!) $\endgroup$ – Matt Aug 1 '13 at 1:26
  • $\begingroup$ Definitely if you limit yourself to certain kinds of p(Z|X,Y) you can do something. I omitted to mention that the IB algorithm itself assumes a markov structure on the variables that allows the alternating optimization to proceed. But in full generality the problem is likely to be hard. I suspect though that you don't mean LP so much as convex program ? because the terms involved are logs, which are nonlinear. $\endgroup$ – Suresh Venkat Aug 1 '13 at 16:57
  • 1
    $\begingroup$ 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)$). $\endgroup$ – Matt Aug 1 '13 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.