<p>In one form, your question is actually a clustering question that is addressed by the <a href="http://en.wikipedia.org/wiki/Information_bottleneck_method">information bottleneck method</a>. </p>

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

<p>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. </p>

CC BY-SA 3.0
2013-08-01T01:13:46.613Z
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.
Matt
CC BY-SA 3.0
2013-08-01T01:26:59.717Z
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
CC BY-SA 3.0
2013-08-01T16:57:02.453Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-08-01T21:42:27.050Z
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
CC BY-SA 3.0
2013-07-30T15:30:06.697Z
2013-07-30T15:30:06.697Z
Suresh Venkat
<p>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.</p>

<p>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$).</p>

<p>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.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2013-07-29T20:53:37.073Z
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.
CC BY-SA 3.0
2013-07-31T15:43:51.867Z
Note that this is a duplicate of http://mathoverflow.net/questions/138043/given-discrete-rvs-x-y-find-z-s-t-izx-is-high-and-izy-is-low-known-p#comment356333_138043
minar
CC BY-SA 3.0
2013-08-02T05:29:30.140Z
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.
<reference-request><it.information-theory><shannon-entropy>
Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. -- known problem?
Matt
# Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. -- known problem?

(Asked by: username_0 on 2013-07-28)

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!

**Tags:** reference-request, it.information-theory, shannon-entropy

> **Comments:**
> **username_1**: 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?  
> **username_2**: Note that this is a duplicate of http://mathoverflow.net/questions/138043/given-discrete-rvs-x-y-find-z-s-t-izx-is-high-and-izy-is-low-known-p#comment356333_138043  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_3 on 2013-07-30. Score: 5 | Accepted answer

In one form, your question is actually a clustering question that is addressed by the [information bottleneck method](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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!)  
> **username_3**: 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.  
> **username_0**: 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)$).  

---

