"Entropy" proof of Brunn-Minkowski Inequality?

Question

I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality.

The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then

$$ m(A+B)^{1/d} \geq m(A)^{1/d} + m(B)^{1/d} $$

where $A+B = \{ a+b: a \in A, b \in B\}$ is the Minkowski sum.

The entropy power inequality states that if $X$ and $Y$ are independent random variables, and $H(X) = \int f(x) \ln f(x) \, dx$ then

$$ e^{2H(X+Y)/d} \geq e^{2H(X)/d}+ e^{2H(Y)/d}$$

If you plug in Gaussian random variables with respective covariance matrices $X = N(0,C_1)$ and $Y = N(0,C_2)$ then you get the version for boxes:

$$ \det(C_1+C_2)^{1/d} \geq \det(C_1)^{1/d} + \det(C_2)^{1/d}$$

I would like to understand better why Convex geometry should have anything to do with information theory, and that the natural probability distributions are associated to a convex set.

---

The article by Gardner has the "ancestor" of the Brunn-Minkowski inequality as the Brascamp-Lieb inequality, while the Entropy power inequality follows from Young's inequality.

• Brunn-Minkowski Inequality
• Brascamp-Lieb inequality
• Young inequality

In that case, my question is what role to convex polygons have there?

---

To me seen seems a "light bulb" these difficult inequalities from functional analysis are based on intuition from convex geometry - especially since nobody draws pictures in a functional analysis textbook.

Answer 1

The similarity between the entropy power inequality and the Brunn-Minkowski inequality is not directly related to convexity - after all, Brunn-Minkowski can be generalised to bounded open sets that are not necessarily convex. (However, many of the proofs of both inequalities use ideas from convexity theory, of course.)

Taking the microstate (i.e. Boltzmann) interpretation of entropy, one can heuristically view the entropy power inequality as a high-dimensional "99%" analogue of Brunn-Minkowski, in which one considers the "99%-sumset" $A \stackrel{99\%}{+} B$ of two high-dimensional sets A and B (this is a somewhat vaguely defined concept, but roughly speaking it is the bulk of the support of two random variables distributed on A and B respectively) rather than the "100%-sumset" A+B. However, thanks to the concentration of measure phenomenon, the 99%-sumset is considerably smaller than the 100%-sumset in high dimensions, leading to the additional exponent of 2 in the entropy power inequality. For instance, consider in high dimensions two balls $B(0,R)$, $B(0,r)$ of radii $R,r$ respectively. Their 100%-sumset is $B(0,R+r)$ of course. But if one takes a random element of $B(0,R)$ and adds it to a random element of $B(0,r)$, the sum concentrates in a much smaller ball - asymptotically, $B(0,\sqrt{R^2+r^2})$ (in fact it concentrates to the boundary of this ball). This boils down to the basic fact that pairs of vectors in high dimensions are typically almost orthogonal to each other. So one morally has

$$ B(0,R) \stackrel{99\%}{+} B(0,r) = B(0,\sqrt{R^2+r^2}) \qquad (1)$$

in the high-dimensional limit.

Anyway, the EPI can be thought of as a rigorous formulation of a ``99% Brunn-Minkowski inequality''

$$ |A \stackrel{99\%}{+} B|^{1/N} \geq \sqrt{ (|A|^{1/N})^2 + (|B|^{1/N})^2 } \qquad (2)$$

in the high-dimensional limit $N \to \infty$ (with $A,B \subset \mathbb{R}^N$ varying appropriately with $N$), which is of course consistent with (1). To see this interpretation, one observes from the microstate interpretation of entropy that if $X$ is a continuous random variable on $\mathbb{R}^n$ with a nice distribution function (e.g. $C^\infty_c$), and $M$ is large, then taking $M$ independent copies $X_1,\dots,X_M$ of $X$ gives a random vector $X^{\otimes M} := (X_1,\dots,X_M)$ in $\mathbb{R}^{N}$ for $N := Mn$ which (by the asymptotic equipartition property) is concentrated in a subset of $\mathbb{R}^N$ of measure $e^{M (H(X)+o(1))}$ in the limit $M \to \infty$ (this is a nice calculation using Stirling's formula; it may help to first work out the case when the probability distribution of $X$ is a simple function rather than a test function). Similarly, if $Y$ is another random variable independent of $X$, then $Y^{\otimes M}$ will be concentrated in a set of measure $e^{M(H(Y)+o(1))}$, while $(X+Y)^{\otimes M}$ is concentrated in a set of measure $e^{M(H(X+Y)+o(1))}$. EPI is then morally a consequence of (2) in the limit $M \to \infty$.

Despite the significant differences between the $99\%$-sumset and $100\%$-sumset in high dimensions, it is still good to think of these concepts as being closely analogous, so that almost any sumset inequality should have an entropy counterpart and vice versa (although in most cases we do not have a direct logical implication between the sumset inequality and the entropy inequality; instead, the inequalities typically have analogous, but not completely identical, proofs). See e.g. this recent paper of Kontoyiannis and Madiman (and the references therein) for some instances of this.

EDIT: Of course, by bounding the $99\%$-sumset by the $100\%$-sumset one can get some connection between the two types of inequalities, but usually one gets an inferior estimate when one uses this approach (it completely ignores the effect of concentration of measure), so this is not the "right" way to relate sumset inequalities with their entropy counterparts. For instance, by directly applying the EPI to uniform random variables on $A,B \subset \mathbb{R}^n$ and then using Jensen's inequality, one only gets a weak form $$ |A+B|^{1/n} \geq \sqrt{ (|A|^{1/n})^2 + (|B|^{1/n})^2 }$$ of the Brunn-Minkowski inequality (compare with (2)). The problem here, of course, is that the sum of two uniformly distributed independent random variables is almost never uniformly distributed.

Answer 2

$\newcommand{\R}{\mathbb{R}}$Actually, for compact subsets $A, B\subset \R^n$, the inequality \begin{equation*} m(A+B)^{1/n} \ge m(A)^{1/n} + m(B)^{1/n} \end{equation*} is ultimately nothing but the convexity of $\log(1+e^x)$ in disguise (whose convexity in turn follows immediately from the AM-GM inequality).

This idea, and the entire inductive proof may be found in Theorem 2.3.9, Notions of Convexity, L. Hörmander (2007, Birkhäuser); this is a superb book which anybody with interest in convexity should definitely own!

The idea of the proof is to show this inequality when $A$ and $B$ are unions of finitely many disjoint products of intervals, by induction over the number of intervals that make up $A$ and $B$.

I'll just cite the base case: here $A$ and $B$ are intervals of side lengths $a_1,\ldots,a_k$ and $b_1,\ldots,b_k$, then

\begin{equation*} m(A)^{1/n} +m(B)^{1/n} = \prod\nolimits_j a_j^{1/n} + \prod\nolimits_j b_j^{1/n} \le \prod\nolimits_j (a_j+b_j)^{1/n}, \end{equation*} where the final inequality follows from homogeneity of terms on both sides of the inequality upon combination with convexity of $\log(1+e^x)$.

Answer 3

Regarding your question "I would like to understand better why Convex geometry should have anything to do with information theory, and that the natural probability distributions are associated to a convex set.", James Melbourne, Peng Xu and I recently wrote a survey article (https://arxiv.org/abs/1604.04225) that exhaustively explores parallels between information theory and convex geometry, including in particular the resemblance between the Brunn-Minkowski inequality (BMI) and the entropy power inequality (EPI).

Let me elucidate some of the key points:

1) As Terry points out, a priori the resemblance between the two inequalities has nothing to do with convexity. Indeed, the BMI holds for arbitrary Borel sets in $\mathbb{R}^d$, while the EPI holds for arbitrary Borel probability measures on $\mathbb{R}^d$. (For the latter, one should use the convention that $N(X)=e^{2h(X)/d}$ is set to be 0 if the entropy $h(X)=-\int f\log f$ with $f$ being the density of $X$ is not defined or if the distribution of $X$ does not have a density. See Bobkov and Chistyakov, "Entropy Power Inequality for the Rényi Entropy", IEEE Trans. on Info. Theory, 2015, for why this convention is essential.)

2) Both the BMI and EPI can be seen as special cases of Rényi entropy inequalities-- one way to see this is via Young's inequality with sharp constant as pointed out by Ofer (indeed, Dembo-Cover-Thomas noted that the Young-Beckner inequality can be rewritten in a form similar to the EPI but with three different Rényi entropies showing up), and the other is to see it via a rearrangement-based unification developed in this paper of Liyao Wang and myself: https://arxiv.org/abs/1307.6018. The latter unification, which is based on the Rogers-Brascamp-Lieb-Luttinger rearrangement inequality, has the following rather neat formulation: $$ (1) \quad\quad\quad h_p(X_1 + \cdots + X_k)\geq h_p(X_1^* + \cdots + X_k^*) $$ where $h_p(X)=\frac{1}{1-p}\log \int f^p$ is the Rényi entropy of $X$ of order $p$, and for any $X$ with density $f$, $X^*$ is a random vector drawn from the density $f^*$ that is the spherically symmetric, decreasing rearrangement of $f$. Note that $h_1(X)$ is just the Shannon entropy $h(X)$, $h_0(X)=\log |K|$ if $K$ is the support of $X$, and $h_\infty(X)=\log \|f\|_\infty$.

3) To see that (1) is a valid unification, the following observation is useful. The BMI can be rewritten in the form $|A_1 +A_2|\geq |B_1+B_2|$ where $B_i$ are Euclidean balls satisfying $|B_i|=|A_i|$ for each $i$. Similarly the EPI can rewritten in the form $N(X_1+X_2)\geq N(Z_1+Z_2)$ where $Z_i$ are independent, spherically symmetric Gaussian random vectors satisfying $N(X_i)=N(Z_i)$ for each $i$. Now we see that the $p=0$ case of the inequality (1) is precisely this alternate form of the BMI. Furthermore, as shown in our paper with Wang, the EPI can be derived from the $p=1$ version of (1) (which in turn can be seen as a strengthening of the EPI, in the sense that it inserts the term $h(X_1^* + \cdots + X_k^*)$ in between the terms $h(X_1 + \cdots + X_k)$ and $h(Z_1 + \cdots + Z_k)$ that appear in the alternate form of the EPI).

4) There is a special role for convexity in the Brunn-Minkowski world, of course. Even though the BMI itself holds for much more general sets, many of the more sophisticated results in convex geometry (examples include the Rogers-Shephard inequality, mixed volumes and the Alexandrov-Fenchel theory, and the reverse Brunn-Minkowski inequality of V. Milman that plays an important role in geometric functional analysis) are special to convex sets. There is, as you suspected, an analogue in the world of probability measures. Indeed, C. Borell developed in the 1970's a beautiful and historically underappreciated theory of "convex measures"-- of which the more well known class of log-concave measures forms a distinguished subset. Let us say (I am skipping some fine points so as not to make this answer too long) that a measure is log-concave when the logarithm of its density is log-concave; thus log-concave measures include all Gaussian measures, uniform measures on convex bodies, exponential measures etc. Then it turns out that many of the inequalities that hold for convex sets but not general sets have analogues that can be stated as entropy inequalities holding for log-concave probability measures but not general probability measures. This story is only partially developed and there remain many interesting open questions; all of what is known until late 2016 together with many open questions are described in our survey at https://arxiv.org/abs/1604.04225.

Answer 4

This is not a full answer but rather a too-long comment:

Both the entropy power inequality (EPI) and the (general, not just for convex sets) Brunn-Minkowski inequality follow from Young's inequality. See section III-B in http://www-isl.stanford.edu/people/cover/papers/dembo_cover_thomas_91.pdf So it is not that they come from different basic inequalities.

On the other hand, as you point out, EPI implies Minkowski's inequality $$|\det (A+B)|^{1/n} \geq |\det (A)|^{1/n}+|\det (B)|^{1/n}$$ for positive definite $A,B$. In turns, it implies the BM for boxes. There is an argument then (the Hadwiger-Ohmann bisection, see page 12 in the article of Gardner that you quote) that transfers the inequality to finite union of boxes, and hence to general Borel sets. However, there is nothing special about convex sets in this argument.

Answer 5

I'm a bit hesitant to resurrect an old post, but as a result of some of the things I worked on recently, I'd like to share a new answer to the question in the title. Hopefully some will find it interesting.

First, one bit of notation. For random vectors $X,Y$ defined on a common probability space, let $I(X;Y):= H(X)+H(Y) - H(X,Y)$ denote their mutual information.  This quantity is nonnegative, and identically zero iff $X,Y$ are independent.

Now, for random vectors $X,Y$ (of dimension $n$) with given marginals and any $\zeta\geq 0$, a recent result by Efe Aras and myself [5] implies \begin{align} e^{2 H(X)/n} + e^{2 H(Y)/n} + 2 {(1-e^{-2 \zeta/n})^{1/2}}e^{H(X)/n}e^{H(Y)/n} \leq \sup_{\text{couplings of }X,Y : I(X;Y)\leq \zeta} e^{2 H(X+Y)/n}, \tag{1}\label{ISIT2021} \end{align} where the supremum is over all couplings of $X,Y$ such that $I(X;Y)\leq \zeta$. If $\zeta=0$, then the only admissible coupling is the one where $X$ and $Y$ are independent, recovering the Shannon-Stam entropy power inequality (EPI): $$e^{2H(X)/n} + e^{2H(Y)/n}   \leq  e^{2H(X+Y)/n}.$$ On the other hand, if $\zeta=+\infty$, then we find  \begin{align}e^{H(X)/n} + e^{H(Y)/n}   \leq \sup_{\text{couplings of }X,Y} e^{H(X+Y)/n},\tag{2}\label{entropyBM} \end{align} where the supremum is now unrestricted, over all couplings of $X$ and $Y$.   Roughly speaking, by transitioning from independence to dependence, we gracefully transition from exponent 2 to 1, which is a salient difference between the EPI and the Brunn-Minkowski inequality (BMI), as pointed out by Terry Tao.  So, one might consider this as an explanation of how the BMI can be seen to emerge from a general relationship on Shannon entropies. More specifically, the above demonstrates how the EPI and BMI can be thought of as occupying opposite extremes in a continuum of entropy inequalities, rather than as one inequality implying the other. (As a remark, \eqref{ISIT2021} is sharp for all $\zeta\in [0,+\infty]$, as seen by testing on Gaussian vectors.)

To clarify why \eqref{entropyBM} implies the BMI, note that if $X$ is supported on a compact set $K$, then $e^{H(X)}\leq m(K)$, with equality iff $X$ is uniformly distributed.  Thus, for $X$ and $Y$ uniformly distributed on compact sets $K,L\subset \mathbb{R}^n$, respectively, the sum $X+Y$ is supported on the Minkowski sum $K+L$, and \eqref{entropyBM} gives: $$ m(K)^{1/n} + m(L)^{1/n}   \leq \sup_{\text{couplings of }X,Y} e^{H(X+Y)/n} \leq m(K+L)^{1/n}.   $$ The slack in the second inequality is governed precisely by the relative entropy between the distribution of $X+Y$ and the uniform distribution on $K+L$, minimized over all couplings. In this sense, it gives a quantitative reinforcement of Terry Tao's last sentence:

The problem here, of course, is that the sum of two uniformly distributed independent random variables is almost never uniformly distributed.

except we can strike the word independent.

I'll close by saying a few words about how \eqref{ISIT2021} comes about. In the Gardner figure reproduced above, one can place a larger family of inequalities at the top of the hierarchy that implies the Brascamp-Lieb (B-L) inequalities, the Barthe inequality, and the reverse Young inequality. Jingbo Liu (together with myself, Cuff and Verdu) introduced this family of inequalities in [1], and called them "forward-reverse" B-L inequalities because they simultaneously generalize the "reverse" B-L inequality due to Barthe, as well as the original forward/direct B-L inequalities. In their 2009 paper, Carlen and Cordero-Erausquin observed that the direct B-L inequalities have an equivalent dual formulation in terms of Shannon entropies [2]. The same can be said for the class of forward-reverse inequalities; it was this connection to entropies that motivated our original study of the forward-reverse inequalities. Inequality \eqref{ISIT2021} can be considered as one instance of the latter in the Euclidean setting, which retains much of the nice structure Bennett, Carberry, Christ and Tao [3] described for the direct B-L inequalities (see [4] for the forward-reverse setting). Thus, coming back to the original post, it is possible to see how everything fits neatly into a larger hierarchy than the one depicted by Gardner (or, rather, an entropic dual formulation of Gardner's hierarchy), where the "entropy connection" between the EPI and BMI can be made more transparent.

Of course, as Mokshay Madiman pointed out in his answer, both the EPI and BMI can be obtained as limiting cases of Young's inequality, which can be stated in terms of three different Rényi entropies, thereby giving some kind of "entropy" proof of the BMI. However, I think the spirit of the original question was asking about Shannon entropies, for which this answer might be more satisfactory.

---

[1] Liu, Jingbo, Courtade, Thomas A., Cuff, Paul W., & Verdú, Sergio. A forward-reverse Brascamp-Lieb inequality: Entropic duality and Gaussian optimality. Entropy, Special Issue on Information Inequalities, 20.6 (2018), 418.

[2] Carlen, Eric A., and Dario Cordero–Erausquin. Subadditivity of the entropy and its relation to Brascamp–Lieb type inequalities. Geometric and Functional Analysis 19.2 (2009): 373-405.

[3] Bennett, Jonathan, Anthony Carbery, Michael Christ, and Terence Tao. The Brascamp–Lieb inequalities: finiteness, structure and extremals. Geometric and Functional Analysis 17, no. 5 (2008): 1343-1415.

[4] Courtade, Thomas A., and Jingbo Liu. Euclidean forward–reverse Brascamp–Lieb inequalities: Finiteness, structure, and extremals. The Journal of Geometric Analysis 31.4 (2021): 3300-3350.

[5] Aras, Efe, and Courtade, Thomas A. Sharp Maximum Entropy Comparisons. Proc. of the 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1504-1509. IEEE, 2021.