Log sum inequality explained

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

Statement

Let

a _{1,\ldots,a} _{n} and b _{1,\ldots,b} _{n} be nonnegative numbers. Denote the sum of all a _{i} s by a and the sum of all b _{i} s by b . The log sum inequality states that\sum ^{n} _{i =1} a _{i log (a _{i})/(b _{i})} \geq a log (a)/(b) ,

with equality if and only if

(a _{i})/(b _{i}) are equal for all i , in other words a _{i} = c b _{i} for all i .

(Take

a _{ilog} (a _{i})/(b _{i}) to be 0 if a _{i=0} and inf ty if a _{i>0,} b _{i=0} . These are the limiting values obtained as the relevant number tends to 0 .)

Proof

Notice that after setting

f(x) = x log x we have\begin{align} \sum ^{n} _{i =1} a _{i log (a _{i})/(b _{i})} & {} = \sum ^{n} _{i =1} b _{i} f\left( (a _{i})/(b _{i}) \right) = b\sum ^{n} _{i =1} (b _{i})/(f\left( b) (a _{i})/(b _{i}) \right) \\ & {} \geq b f\left(\sum ^{n} _{i =1} (b _{i})/(b) (a _{i})/(b _{i}) \right) = b f\left( (1)/(b) \sum ^{n} _{i =1} a _{i\right) =} b f\left( (a)/(b) \right) \\ & {} = a log (a)/(b) , \end{align} where the inequality follows from Jensen's inequality since (b _{i})/(b) \geq 0 , \sum ^{n (b _{i})/(b)} _{i =1} = 1 , and f is convex.

Generalizations

The inequality remains valid for

n =inf ty provided that a< inf ty and b< inf ty .The proof above holds for any function g such that f(x) = xg(x) 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

a _{1,} a _{2} … a _{n} and b _{1,} b _{2} … b _{n} are positive real numbers with a _{1+} a _{2} … + a _{n=a} and b _{1} + b _{2} … + b _{n=b} , and k \geq 0 , then \sum ^{n} _{i =1} a _{i} log \left( (a _{i})/(b _{i}) + k \right) \geq a log \left( (a)/(b) + k\right) . ^[1]

Applications

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. One proof uses the log sum inequality.

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

References

• Book: Thomas M. . Cover . Joy A. . Thomas . Elements of Information Theory . Wiley . Hoboken, New Jersey . 978-0-471-24195-9. 1991 .
• I. . Csiszár . Imre Csiszár . P. . Shields . 2004 . Information Theory and Statistics: A Tutorial . Foundations and Trends in Communications and Information Theory . 1 . 4 . 417 - 528 . 10.1561/0100000004 . 2009-06-14.
• T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. .
• Information Theory course materials, Utah State University http://ocw.usu.edu/Electrical_and_Computer_Engineering/Information_Theory/lecture3.pdf. Retrieved on 2009-06-14.
• Book: MacKay, David J.C. . David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. 2003. 0-521-64298-1.

Notes and References

1. F. M. Dannan, P. Neff, C. Thiel . On the sum of squared logarithms inequality and related inequalities . Journal of Mathematical Inequalities . 2016 . 10 . 1 . 1–17 . 10.7153/jmi-10-01 . 23953925 . 12 January 2023.