University Homepage School Homepage School Contacts School Search

Lecture 7, Friday w4, 2014-10-10

Things we covered:

• Definition of a complete code (left-over from last time).
• Kullback–Leibler (KL) divergence
• Gibb’s inequality.
• Definitions of (strictly) convex/concave functions.
• Jensen’s inequality, proving Gibb’s and other inequalities with it.

Check your progress

Things you should be able to do after reviewing the lecture:

• Given an incomplete symbol code, describe a mechanism to make a better code. (We’re about to go beyond simple symbol codes. Most real compression systems, like gzip, are not complete, but making them complete would be non-trivial!)
• Understand how to apply Jensen’s inequality to a new situation, and interpret the case when there is equality. Try to solve Example 2.15 on p35 of MacKay without looking at the solution. Be careful, as the solution is right there!

Recommended reading

We finished the last few ‘week 3’ slides and covered the first 5 slides in the ‘week 4’ slides. Ask on NB if anything else is unclear, or too compressed.

Gibb’s inequality and Jensen’s inequality are covered on MacKay pp34–36.

---

This page maintained by Iain Murray.
Last updated: 2014/10/10 17:16:39