"You should call it entropy for two reasons: first because that is what the formula is in statistical mechanics but second and more important, as nobody knows what entropy is, whenever you use the term you will always be at an advantage!" -John von Neumman

ECE-5583/TCOM-5583: Information Theory

Prerequisites: ECE 4523 or instructor permission

This is a graduate introductory course in information theory targeted to graduate and senior students. The goal is to both inspire students with the thought-provoking ideas of information theory and provide them enough knowledge necessary for further study of the subject.

Course Outline:

  1. Overview
  2. Review of probability theory
  3. Lossless source coding theory, Huffmann coding, and introduction to Arithmetic coding
  4. Asymptotic equipartition property (AEP), typicality and joint typicality
  5. Entropy, conditional entropy, mutual information, and their properties
  6. Introducing project
  7. Channel coding theory, capacity, and Fano’s inequality
  8. Continuous random variables, differential entropy, Gaussian source, and Gaussian channel
  9. Bandlimited AWGN channel, parallel Gaussian channels, waterfilling and inverse waterfilling
  10. Error correcting codes, linear codes, and introduction to low-density parity check code
  11. Digital fountain, luby code, raptor code
  12. Lossy source coding theory and rate-distortion function
  13. Duality of source and channel coding, separation theorem
  14. Method of type, large deviation theory, maximum entropy principle
  15. Network information theory

Textbook

“Elements of Information Theory,” by Cover and Thomas, New York: Wiley.

Second edition is quite a bit better. But 1st edition is okay too, given that it is way cheaper in Amazon. You probably can get one below 20 bucks.

Auxiliary and Reference Material:

  • Shannon, C. E. (1948) A mathematical theory of communication. Bell Sys. Tech. J. 27: 379-423, 623-656.
  • Information Theory, Inference, and Learning Algorithms,” by David J.C. Mackay, Cambridge: Cambridge University Press.
  • R. W. Yeung, “On entropy, information inequalities, and Groups.”
  • "Law of Large Number," by Terry Tao.
  •  “A First Course in Information Theory,” by Raymond W. Yeung, New York: Springer.
  •  “Information Theory and Reliable Communication,” by R. Gallager, New York: Wiley.
  • “Information Theory,” by Csiszar and Korner, New York: Academic Press.
  • Entropy and Information Theory,” by R. M. Gray, Springer-Verlag, 1990.
  • Probability, Random Processes, and Ergodic Properties,” by R. M. Gray, Springer-Verlag, 1988.
  • J. S. Yedidia, W. T. Freeman, and Y. Weiss, "Understanding Belief Propagation and its Generalizations," in Exploring Artificial Intelligence in the New Millennium: Science and Technology Books, 2003.
  • P. A. Chou and Y. Wu, "Network Coding for the Internet and Wireless Networks," Signal Processing Magazine, IEEE, vol. 24, pp. 77-85, 2007.
  • S. Katti, S. Shintre, S. Jaggi, D. Katabi, and M. Medard, "Real Network Codes," in Allerton, 2007.
  • D. J. C. MacKay, "Fountain codes," IEE Communications, vol. 152, pp. 1062-1068, 2005.
  • S. Verdu, "Fifty years of Shannon theory," Information Theory, IEEE Transactions on, vol. 44, pp. 2057-2078, 1998.
  • A. R. Calderbank, "The art of signaling: fifty years of coding theory," Information Theory, IEEE Transactions on, vol. 44, pp. 2561-2595, 1998.
  • I. Csiszar, "The method of types [information theory]," Information Theory, IEEE Transactions on, vol. 44, pp. 2505-2523, 1998.
  • Information Theoretic Inequality Prover
  • Xian Qian, Xiaoqian Jiang, Qi Zhang, Xuanjng Huang, and Lide Wu, "Sparse higher order conditional random fields for improved sequence labeling," ICML, 2009.

Grading

Like last year, I want to make grading very concrete this time. You will get

  • A: Exam average > 85%
  • B: Exam average > 70%
  • C: Exam average > 50%
  • D: Otherwise.

Be forewarned, getting an A in this course is neither automatic nor easy. You will need some real effort and high maturity on your math ability.


Project (Extra Credit)

I expect a screencast and a report on a relevant topic including what, why, and how. A good report should reflect the understanding of the author on the topic. You may do a group project if you want and you may submit one project report but you need to show how your work is separated. But I expect one screencast for each individual even for a group project. I will grade your project based on:

  1. The relevancy and depth (difficulty) of the chosen topic
  2. How much you understand the materials that I can perceive
  3. How much effort you have paid that I can perceive

Here are some suggestions for potential projects.

  • Polar Code
  • Gaussian Process Regression
  • Finite Rate of Innovation
  • Coprime Sampling
  • Relevance Vector Machine
  • Locality Sensitive Hashing

You should submit your report through d2l (there is a dropbox folder "project upload" where you can upload to) and there is a hard deadline of 11:59 PM, Dec 15, 2014. In the report, you also have to specify the link(s) to your screencast(s). You may use any online video server. But I guess YouTube is the probably easiest. Be sure to set the video to either unlisted or public so that others can access to it.


 

Calendar (Tentative)

  Summary Course notes Homework Reference
8-18-2014 Overview, Shannon Entropy, An Example, Lossless Source Coding, Instantaneous Codes 01 overview.rar 02 probability.pdf
8-20-2014 Kraft Inequality, Uniquely Decodability and Kraft Inequality 03 lossless source coding.zip   [ASH '65 p. 5-11], axiom_note.pdf
8-25-2014 S-F-E Coding, Arithmetic Coding      
8-27-2014 AEP, An Example, Lower Bound of Source Coding (Part 1, Part 2), Summary of Source Coding Theory 04 AEP.rar    
9-3-2014 Mutual Information, Conditional Mutual Information, Conditional Entropy, Other Information Measures, Bounds on Information Measures      
9-8-2014 More on Mutual Information and Conditional Mutual Information, An Example, Data Processing Inequality 05 information measures.rar  
9-10-2014 Introduction to Channel Coding Theorem, BSC     conditional relative entropy, supplimentary for Jensen Inequality
9-15-2014 Forward proof of Channel Coding Theorem      
9-17-2014 Fano's inequality, Converse Proof of Channel Coding Theorem channel_coding_theorem.pdf  
9-22-2014 MAP estimator, Maximum Likelihood Estimator    
9-24-2014 Conjugate Prior, Multivariate Gaussian Distribution Notes on Multivariate Gaussian  
9-29-2014

Marginalization of Multivariate Gussian Distribution

   
10-1-2014 Conditioning of Multivariate Gaussian Distribution
     
10-6-2014 Product of Gaussian Pdfs 07 differential entropy.rar    
10-8-2014 Mixture of Gaussians 08 Gaussian channel.rar    
10-13-2014 Gaussian Process channel coding chapter,    
10-15-2014 Test 1  
10-20-2014 Differential Entropy, Gaussian Channel      
10-22-2014 Bandlimited Gaussian Chanel 09 error correcting codes.rar    
10-27-2014 Principal Component Analysis      
10-29-2014 Waterfilling for Parallel Gaussian Channels, Linear Code, Hamming Code, Trellis Coded Modulation, Viterbi Algorithm      
11-1-2014 Belief Propagation, Forward Backward Algorithm      
11-6-2014 Low Density Parity Check Code    
11-10-2014 Convolutional Codes    
11-12-2014 Turbo Codes      
11-17-2014 Campus closed    
11-19-2014 Bayesian Compressed Sensing     Bayesian CS paper
11-24-2014 ICA    
11-26-2014 Thanskgiving      
12-8-2014 Final      

Some lecture notes are available in Windows Journal Viewer format.