The log sum inequality is used for proving theorems in information theory.

Statement

edit

Let   and   be nonnegative numbers. Denote the sum of all  s by   and the sum of all  s by  . The log sum inequality states that

 

with equality if and only if   are equal for all  , in other words   for all  .[1]

(Take   to be   if   and   if  . These are the limiting values obtained as the relevant number tends to  .)[1]

Proof

edit

Notice that after setting   we have

 

where the inequality follows from Jensen's inequality since  ,  , and   is convex.[1]

Generalizations

edit

The inequality remains valid for   provided that   and  .[citation needed] The proof above holds for any function   such that   is convex, such as all continuous non-decreasing functions. Generalizations to non-decreasing functions other than the logarithm is given in Csiszár, 2004.

Another generalization is due to Dannan, Neff and Thiel, who showed that if   and   are positive real numbers with   and  , and  , then  . [2]

Applications

edit

The log sum inequality can be used to prove inequalities in information theory. Gibbs' inequality states that the Kullback-Leibler divergence is non-negative, and equal to zero precisely if its arguments are equal.[3] One proof uses the log sum inequality.

The inequality can also prove convexity of Kullback-Leibler divergence.[4]

Notes

edit
  1. ^ a b c d Cover & Thomas (1991), p. 29.
  2. ^ F. M. Dannan, P. Neff, C. Thiel (2016). "On the sum of squared logarithms inequality and related inequalities" (PDF). Journal of Mathematical Inequalities. 10 (1): 1–17. doi:10.7153/jmi-10-01. S2CID 23953925. Retrieved 12 January 2023.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  3. ^ MacKay (2003), p. 34.
  4. ^ Cover & Thomas (1991), p. 30.

References

edit