Log sum inequality

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

Statement

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

Notice that after setting we have

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

Generalizations

The inequality remains valid for provided that and . 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.

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

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

Notes

  1. Cover & Thomas (1991), p. 29.
  2. MacKay (2003), p. 34.
  3. Cover & Thomas (1991), p. 30.
gollark: 33L of liquiescent bee slurry.
gollark: You should have a way to *upload* HTML, and maybe ZIPs too.
gollark: So daily stuff shows up a bit.
gollark: It's just fixed at 6 hours width.
gollark: I didn't. The FFT was very boring.

References

  • Thomas M. Cover; Joy A. Thomas (1991). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9.
  • Csiszár, I.; Shields, P. (2004). "Information Theory and Statistics: A Tutorial" (PDF). Foundations and Trends in Communications and Information Theory. 1 (4): 417–528. doi:10.1561/0100000004. Retrieved 2009-06-14.
  • T.S. Han, K. Kobayashi, Mathematics of information and coding. American Mathematical Society, 2001. ISBN 0-8218-0534-7.
  • Information Theory course materials, Utah State University . Retrieved on 2009-06-14.
  • MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.