Brascamp–Lieb inequality

In mathematics, the Brascamp–Lieb inequality is either of two inequalities. The first is a result in geometry concerning integrable functions on n-dimensional Euclidean space . It generalizes the Loomis–Whitney inequality and Hölder's inequality. The second is a result of probability theory which gives a concentration inequality for log-concave probability distributions. Both are named after Herm Jan Brascamp and Elliott H. Lieb.

The geometric inequality

edit

Fix natural numbers m and n. For 1 ≤ i ≤ m, let ni ∈ N and let ci > 0 so that

 

Choose non-negative, integrable functions

 

and surjective linear maps

 

Then the following inequality holds:

 

where D is given by

 

Another way to state this is that the constant D is what one would obtain by restricting attention to the case in which each   is a centered Gaussian function, namely  .[1]

Alternative forms

edit

Consider a probability density function  . This probability density function   is said to be a log-concave measure if the   function is convex. Such probability density functions have tails which decay exponentially fast, so most of the probability mass resides in a small region around the mode of  . The Brascamp–Lieb inequality gives another characterization of the compactness of   by bounding the mean of any statistic  .

Formally, let   be any derivable function. The Brascamp–Lieb inequality reads:

 

where H is the Hessian and   is the Nabla symbol.[2]

BCCT inequality

edit

The inequality is generalized in 2008[3] to account for both continuous and discrete cases, and for all linear maps, with precise estimates on the constant.

Definition: the Brascamp-Lieb datum (BL datum)

  •  .
  •  .
  •  .
  •   are linear surjections, with zero common kernel:  .
  • Call   a Brascamp-Lieb datum (BL datum).

For any   with  , define 


Now define the Brascamp-Lieb constant for the BL datum: 

Theorem — (BCCT, 2007)

  is finite iff  , and for all subspace   of  ,

 

  is reached by gaussians:

  • If   is finite, then there exists some linear operators   such that   achieves the upper bound.
  • If   is infinite, then there exists a sequence of gaussians for which

 

Discrete case

edit

Setup:

  • BL datum defined as  
  •   is the torsion subgroup, that is, the subgroup of finite-order elements.

With this setup, we have (Theorem 2.4,[4] Theorem 3.12 [5])

Theorem — If there exists some   such that

 

Then for all  ,

  and in particular,

 

Note that the constant   is not always tight.

BL polytope

edit

Given BL datum  , the conditions for   are

  •  , and
  • for all subspace   of  , 

Thus, the subset of   that satisfies the above two conditions is a closed convex polytope defined by linear inequalities. This is the BL polytope.

Note that while there are infinitely many possible choices of subspace   of  , there are only finitely many possible equations of  , so the subset is a closed convex polytope.

Similarly we can define the BL polytope for the discrete case.

Relationships to other inequalities

edit

The geometric Brascamp–Lieb inequality

edit

The case of the Brascamp–Lieb inequality in which all the ni are equal to 1 was proved earlier than the general case.[6] In 1989, Keith Ball introduced a "geometric form" of this inequality. Suppose that   are unit vectors in   and   are positive numbers satisfying

 

for all  , and that   are positive measurable functions on  . Then

 

Thus, when the vectors   resolve the inner product the inequality has a particularly simple form: the constant is equal to 1 and the extremal Gaussian densities are identical. Ball used this inequality to estimate volume ratios and isoperimetric quotients for convex sets in [7] and.[8]

There is also a geometric version of the more general inequality in which the maps   are orthogonal projections and

 

where   is the identity operator on  .

Hölder's inequality

edit

Take ni = n, Bi = id, the identity map on  , replacing fi by f1/ci
i
, and let ci = 1 / pi for 1 ≤ i ≤ m. Then

 

and the log-concavity of the determinant of a positive definite matrix implies that D = 1. This yields Hölder's inequality in  :

 

Poincaré inequality

edit

The Brascamp–Lieb inequality is an extension of the Poincaré inequality which only concerns Gaussian probability distributions.[9]

Cramér–Rao bound

edit

The Brascamp–Lieb inequality is also related to the Cramér–Rao bound.[9] While Brascamp–Lieb is an upper-bound, the Cramér–Rao bound lower-bounds the variance of  . The Cramér–Rao bound states

 .

which is very similar to the Brascamp–Lieb inequality in the alternative form shown above.

References

edit
  1. ^ This inequality is in Lieb, Elliott H. (1990). "Gaussian Kernels have only Gaussian Maximizers". Inventiones Mathematicae. 102: 179–208. Bibcode:1990InMat.102..179L. doi:10.1007/bf01233426.
  2. ^ This theorem was originally derived in Brascamp, Herm J.; Lieb, Elliott H. (1976). "On Extensions of the Brunn–Minkowski and Prékopa–Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation". Journal of Functional Analysis. 22 (4): 366–389. doi:10.1016/0022-1236(76)90004-5. Extensions of the inequality can be found in Hargé, Gilles (2008). "Reinforcement of an Inequality due to Brascamp and Lieb". Journal of Functional Analysis. 254 (2): 267–300. doi:10.1016/j.jfa.2007.07.019. and Carlen, Eric A.; Cordero-Erausquin, Dario; Lieb, Elliott H. (2013). "Asymmetric Covariance Estimates of Brascamp-Lieb Type and Related Inequalities for Log-concave Measures". Annales de l'Institut Henri Poincaré B. 49 (1): 1–12. arXiv:1106.0709. Bibcode:2013AIHPB..49....1C. doi:10.1214/11-aihp462.
  3. ^ Bennett, Jonathan; Carbery, Anthony; Christ, Michael; Tao, Terence (2008-01-01). "The Brascamp–Lieb Inequalities: Finiteness, Structure and Extremals". Geometric and Functional Analysis. 17 (5): 1343–1415. doi:10.1007/s00039-007-0619-6. hdl:20.500.11820/b13abfca-453c-4aea-adf6-d7d421cec7a4. ISSN 1420-8970. S2CID 10193995.
  4. ^ Bennett, Jonathan; Carbery, Anthony; Christ, Michael; Tao, Terence (2005-05-31). "Finite bounds for Holder-Brascamp-Lieb multilinear inequalities". arXiv:math/0505691.
  5. ^ Christ, Michael; Demmel, James; Knight, Nicholas; Scanlon, Thomas; Yelick, Katherine (2013-07-31). "Communication lower bounds and optimal algorithms for programs that reference arrays -- Part 1". arXiv:1308.0068 [math.CA].
  6. ^ Brascamp, H. J.; Lieb, E. H. (1976). "Best Constants in Young's Inequality, Its Converse and Its Generalization to More Than Three Functions". Advances in Mathematics. 20 (2): 151–172. doi:10.1016/0001-8708(76)90184-5.
  7. ^ Ball, Keith M. (1989). "Volumes of Sections of Cubes and Related Problems". In Lindenstrauss, Joram; Milman, Vitali D. (eds.). Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics. Vol. 1376. Berlin: Springer. pp. 251–260. doi:10.1007/BFb0090058. ISBN 978-3-540-51303-2.
  8. ^ Ball, Keith M. (1991). "Volume ratios and a reverse isoperimetric inequality". J. London Math. Soc. 44: 351–359. arXiv:math/9201205. doi:10.1112/jlms/s2-44.2.351.
  9. ^ a b Saumard, Adrien; Wellner, Jon A. (2014). "Log-concavity and strong log-concavity: a review". Statistics Surveys. 8: 45–114. doi:10.1214/14-SS107. PMC 4847755. PMID 27134693.