| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Entropy Power Inequality Extensions

    1. Problem 2.1.

      [Peter Herremoës] Consider independent random vectors, $$ \begin{bmatrix} X_1 & Y_1 \end{bmatrix} \in \mathbb{R}^2, \quad \text{ and } \quad \begin{bmatrix} X_2 & Y_2 \end{bmatrix} \in \mathbb{R}^2,$$ with $X$ and $Y$ uncorrelated. The problem is to find a function $f$ universal over the laws of the vectors in the above such that \[I(X_1 + X_2; Y_1 + Y_2) \leq f(I(X_1; Y_1), I(X_2; Y_2)).\] The problem is motivated by a desire to remove the scaling from the entropy power inequalities.
        • Problem 2.2.

          [Abram Kagan] Let $X_1 \sim p_1(X_1; \theta_1)$ defined for all $\theta_1 \in \mathbb{R}$ and $X_2 \sim p_2(X_2; \theta_2)$ defined for all $\theta_2 \in \mathbb{R}$ be random elements of a general nature. Define the Fisher Informations in $X_1$ and $X_2$ as $I_1$ and $I_2$, respectively, i.e. for $i=1,2$, \[I_i = \mathbb{E}\left[\left(\frac{\delta}{\delta \theta_i} \log p_i(X_i; \theta_i)\right)^2\right].\] Consider a statistics $U = f(X_1, X_2)$ with a property \[U \sim p(u; \theta_1, \theta_2) = p(u, \theta_1 + \theta_2).\] For such $U$ that satisfies the above, a version of (a generalization of) the Stam Inequality holds: \[\frac{1}{I_U(\theta)} \geq \frac{1}{I_1(\theta)} + \frac{1}{I_2(\theta)}.\] It is of interest to see if for $U$ with $g(\theta_1, \theta_2): \Theta_1 \times \Theta_2 \rightarrow \Theta$, \[U \sim p(u; \theta_1, \theta_2) = p(u, g(\theta_1, \theta_2)),\] is there an analogy of the Stam Inequality?
            • Problem 2.3.

              [Thomas Courtade] For $X, Y, Z$ independent vectors in $\mathbb{R}^d$ having densities, we define the standard multivariate entropy power as $N(X) \triangleq \exp\left(\frac{2}{d} h(X)\right)$. The conjecture is that \[N(X+Y+Z)N(Z) + N(X) N(Y) \leq N(X+Z)N(Y+Z).\] The above is known to be true when $Z$ is Gaussian, however we additionally desire a direct proof of this known result.

              Note that without the $N(X)N(Y)$ term on the left, this is precisely the submodularity of entropy of sums that follows from standard information inequalities but was first explicitly observed in this paper: M. Madiman, “On the Entropy of Sums”, Proceedings of the 2008 IEEE Information Theory Workshop, Porto, Portugal, May 2008.

              The conjecture may be thought of as a way to strengthen this submodularity.
                • Problem 2.4.

                  [Yonathan Morin] By Zamir-Feder, for any matrix $A$ with \[X = \begin{bmatrix} X_1 & X_2 & \ldots & X_n \end{bmatrix}, \quad \text{ and } \quad \tilde{X} = \begin{bmatrix} \tilde{X}_1 & \tilde{X}_2 & \ldots & \tilde{X}_n \end{bmatrix},\] with components $X_i$ independent and $\tilde{X}_i$ i.i.d. Gaussian such that $h(X_i) = h(\tilde{X}_i)$ for $1 \leq i \leq n$, then \[h(Ax) \geq h(A \tilde{x}).\] The open problems asks if such an inequality is true when the random vector $X$ has dependent components. A simpler version of the open problem is the following. Let $X \in \mathbb{R}^N$ have dependent entries and define $Y = X + Z \in \mathbb{R}^2$ where $Z \in \mathbb{R}^2$ is noise. The open problem looks for an EPI of the form \begin{equation} N(Y) \geq g(N(X), N(Z)) \end{equation} for some function $g(\cdot, \cdot)$. Even simpler still we could take \[X = \begin{bmatrix} X_1 & X_1 \end{bmatrix},\] i.e. $X_1 = X_2$, and seek an EPI of the form in the above with $N(X)$ replaced with $N(X_1)$.
                    • Problem 2.5.

                      [Mokshay Madiman] Let $[n] = \{1, 2, \ldots, n\}$. We define a $d$-dimensional entropy power region as follows: \[\Gamma_d(n) \triangleq \left\{ \begin{bmatrix} N(\sum_{i \in S} X_i) \\ \end{bmatrix} : X_1, \ldots, X_n \in \mathbb{R}^d \text{ independent, random vectors }, S \subseteq [n], S \neq \emptyset \right\}.\] Then we let the entropy power region be \[\Gamma(n) = \cup_{d \geq 1} \Gamma_d(n) \subseteq \mathbb{R}_{+}^{2^n - 1}.\] Let $\mathcal{G}$ be a collection of nonempty subsets of $[n]$. Then given $\mathcal{G}$, we call a function $\beta: \mathcal{G} \rightarrow \mathbb{R}_{+}$ a fractional partition if for each $i \in [n]$, $\sum_{s \in \mathcal{G}: i \in s} \beta_S = 1$. A set function $\nu: 2^{[n]} \rightarrow \mathbb{R}_{+}$ is called fractionally superadditive if \[\nu([n]) \geq \sum_{ s \in \mathcal{G}} \beta_s \nu(s). \] Using these definitions, we define the class of all fractionally superadditive set functions $\nu$ with $\nu(\emptyset) = 0$ as follows \[\Gamma_{FSA}(n) \triangleq \left\{ \begin{bmatrix} \nu(s) \\ \end{bmatrix} : \nu \text{ is fractionally superadditive } \forall \text{ fractional partitions } \beta, S \subseteq [n], S \neq \emptyset \right\}.\] We know that $\Gamma(n) \subseteq \Gamma_{FSA}(n)$ due to Ghassemi and Madiman [arXiv:1704.01177] of which the subset sum EPI of Artstein, Ball, Barthe, and Naor is a special case. Further, we define a set function $\nu$ to be supermodular if \[\nu(s \cup t) + \nu(s \cap t) \geq \nu(s) + \nu(t),\] for all sets $s, t \subset [n]$. If we let $\Gamma_{SM}$ be the class of all supermodular set functions $\nu$ with $\nu(\emptyset) = 0$, then it is known that $\Gamma_{SM}(n) \subseteq \Gamma_{FSA}(n)$ and that $\Gamma(n) \nsubseteq \Gamma_{SM}(n)$ for $n=3$ or more [arXiv:1704.01177].

                      The open problems are the following. First, is the closure of $\Gamma(n)$ convex? It is known that the closure of $\Gamma(n)$ is a log-convex cone. Second, how does one characterize the closure of $\Gamma(3)$? It is known, for example, that the closure of $\Gamma(2)$ equals $\Gamma_{FSA}(2)$.

                          Cite this as: AimPL: Entropy power inequalities, available at http://aimpl.org/entropypower.