1
$\begingroup$

Assume $P \in \mathbb{R}^{n \times n}$ describe the joint distribution of the random variable $J$ over the finite set $\mathcal{X}\times \mathcal{X} $.

I am interested in finding a right stochastic matrix $Q \in \mathbb{R}^{n \times m} , m <n,$ such that mutual information, $I(Q^TPQ)$ is maximized.

I couldn't proceed much with the cost function at hand as it seems tedious to give an expression for the mutual information as a function of matrix entries.

Any help will be appreciated.

Update on what I have tried so far(intuitions):

Suppose we are interested in maximizing the cost function of the form $I(Q_1^TPQ_2)$ such that $Q_1^TPQ_2 \in \mathbb{R}^{m \times m}$ then the maximizers $Q_1,Q_2$ are deterministic matrices, by which I mean each and every row of $Q_1,Q_2$ is either $0$ or $1$ and having the property that both being right stochastic matrices- Birkhoff's Theorem.

In the case of $Q_1=Q_2$, this is no longer the case. Non deterministic matrices can also maximize the cost function.(Simulation evidence)

We can give a upper bound as $|I(P)-I(Q^TPQ)| \le \log \frac{n}{m}$. Since the space of right stochastic matrices of the form $\{Q^TPQ : Q- \text{right stochastic} \}$ is indeed closed and compact, maximizer is guarateed with the search space of right stochastic matrices.

I tried to do entry by entry update of $(Q)_{ij}$ by computing the derivative of the $I(Q^TPQ)$, however it seems "clumsy" when I start writing out the expressions.

Any idea on how to solve the problem of this sort will be appreciable.

$\endgroup$
3
  • 1
    $\begingroup$ You should probably include the rest of the details of your situation. $\endgroup$ Oct 13, 2015 at 10:49
  • 1
    $\begingroup$ The problem is well defined to me. But, defining some details won't hurt. $\endgroup$
    – Memming
    Oct 14, 2015 at 1:29
  • $\begingroup$ I have gained some intuition, I couldn't attempt any way to solve them. However I have added the thoughts I had till now in the post. $\endgroup$
    – lebesgue
    Oct 14, 2015 at 6:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.