32
$\begingroup$

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.

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


enter image description here

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.

$\endgroup$
  • 5
    $\begingroup$ @user36931 I will not dignify your comment with a response $\endgroup$ – john mangual May 23 '14 at 15:32
  • 1
    $\begingroup$ Sorry @john mangual my comment wasn't constructive and was more of a reaction to soft questions in general. My point was that this seems like a fine question to ask a functional analyst over beer or tea, but not in the spirit of mathoverflow.net which is limited in it's function to precise technical questions as opposed to "meta" questions. I'll let others decide if they agree or disagree. $\endgroup$ – user36931 May 23 '14 at 15:46
  • 3
    $\begingroup$ I don't have a good explanation, but there has been a lot of recent work showing that the many geometric properties of convex bodies are special cases of information theoretic properties of log-concave probability densities. Information theoretic-measures such as entropy, covariance matrix, and Fisher information are generalizations of geometric invariants such as volume. Sharp information theoretic inequalities are generalizations of sharp geometric inequalities for convex bodies. The idea is that theorems for "sharp-edged" convex bodies can be generalized to ones for "fuzzy" random vectors. $\endgroup$ – Deane Yang May 25 '14 at 2:59
  • 3
    $\begingroup$ The usual way to construct a random variable corresponding to a body such as an oval or polytope is to use the uniform distribution, but this doesn't always work. What works more often (but still not always) is what my collaborators and I call a "contoured distribution", where the levels sets of the density function are all dilates of the body. In particular, if the body is the unit ball of a norm $\|\cdot\|$, then the corresponding density function could be the "generalized Gaussian" $\exp(-\|x\|^2)$. $\endgroup$ – Deane Yang May 25 '14 at 17:17
  • 1
    $\begingroup$ @johnmangual but you did dignify him by a response. :-) your response: "@user36931 I will not dignify your comment with a response". $\endgroup$ – Alan Mar 4 '17 at 19:08
26
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Terry, you give your usual beautiful explanation of the mathematics, in this case of how the two inequalities are related in higher dimensions. However, what my collaborators and I find particularly intriguing is that the relationship between geometric and information theoretic inequalities seems to hold even for the sharp versions and in all dimensions. I should know why this is so but I don't. $\endgroup$ – Deane Yang May 25 '14 at 17:15
  • 2
    $\begingroup$ If the inequalities in question behave well with respect to Cartesian powers (and both Brunn-Minkowski and EPI do so) then one can deduce the arbitrary-dimension exact form of these inequalities from an asymptotic high-dimension form (this is an instance of the "tensor power trick"). So in many cases one can actually recover the exact theory from the asymptotic theory. $\endgroup$ – Terry Tao May 25 '14 at 18:08
  • $\begingroup$ Good point! Artstein, Klartag, and Milman used the same trick to prove a sharp functional Blaschke-Santalo inequality. But we don't know how to make this work for other types of inequalities. And I forget but does this proof establish the equality conditions? $\endgroup$ – Deane Yang May 25 '14 at 18:20
  • $\begingroup$ @TerryTao A Gaussian random variable doesn't have a support - it could be anywhere - but normally it's within a certain standard deviation. Shannon talks about thinking "logarithmically" and the about sphere on which "most" of the probability is concentrated. And I can practice using the stackrel command $\stackrel{99\%}{+}$. $\endgroup$ – john mangual May 26 '14 at 11:33
  • 1
    $\begingroup$ In connection to this line of thought, it is worth reading "Shannon’s entropy power inequality via restricted Minkowski sums" by S. J. Szarek, D. Voiculescu. The idea of $\stackrel{99\%}+$ is rigorously defined and used in this paper. $\endgroup$ – VSJ Jun 10 '14 at 18:35
17
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I found functional analysis unwieldy and unmotivated. Unfortunately certain limit theorems from combinatorics and random matrix theory do have a large deviations step, so I tried to learn them in some kind of way. Information theory could offer a geometric way of viewing these inequalities. Or I had hoped. I know even less than when I started. $\endgroup$ – john mangual Mar 4 '17 at 3:17
  • 3
    $\begingroup$ There is indeed a geometric way of understanding large deviation results using information theory. For finite alphabets, the classical "method of types" can be used to prove Sanov's theorem (the prototypical result of large deviation theory); this can be found either in the textbook "Elements of Information Theory" by Cover and Thomas, or in the 1998 survey article "The Method of Types" by Csiszár, or in this blog post by Ramon van Handel: blogs.princeton.edu/sas/2013/10/10/lecture-3-sanovs-theorem $\endgroup$ – Mokshay Madiman Mar 4 '17 at 15:11
  • $\begingroup$ For more general alphabets, there is a beautiful geometric approach of Csiszár that builds on his theory of information projections, provided one is interested in the probability that an empirical measure based on an i.i.d. sequence lies in a convex set of probability measures. See his 1984 paper "Sanov property, generalized I-projection, and a conditional limit theorem". $\endgroup$ – Mokshay Madiman Mar 4 '17 at 15:16
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The textbook just says "Brunn-Minkowski... which is a special instance of EPI..." without discussing the long and winding path between the two. It seemed plausiable to show the Gaussian Free Field supported on a domain $A$ had an entropy power equal to $V(A)^{1/d}$. It's still not an "entropy" proof of Brunn-Minkowski $\endgroup$ – john mangual May 25 '14 at 11:31

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.