Advanced topics in information theory
From CYPHYNETS
(→July 14: Rate distortion theory - I) |
|||
Line 100: | Line 100: | ||
=== Aug 11: Wireless networks, cognitive radios === | === Aug 11: Wireless networks, cognitive radios === | ||
=== Aug 18: Multiple access channels, network coding techniques === | === Aug 18: Multiple access channels, network coding techniques === | ||
+ | |||
+ | |||
+ | |||
+ | <math>a=123343534534957349579347593475893475934875893475983457934785+923497239472394723947923742389</math> |
Revision as of 08:03, 30 July 2009
Reading Group: Advanced Topics in Information Theory
Calendar: Summer 2009
Venue: LUMS School of Science & Engineering
Organizer: Abubakr Muhammad
This group meets every week at LUMS to discuss some advanced topics in information theory.
This is a continuation of our formal course at LUMS, CS-683: Information theory (offered most recently in Spring 2008). We hope to cover some advanced topics in information theory as well as its connections to other fundamental disciplines such as statistics, mathematics, physics and technology.
Participants
- Mubasher Beg
- Shahida Jabeem
- Qasim Maqbool
- Muhammad Bilal
- Muzammad Baig
- Hassan Mohy-ud-Din
- Zartash Uzmi
- Shahab Baqai
- Abubakr Muhammad
Topics
Include the following, but not limited to:
- Rate distortion theory
- Network information theory
- Kolmogorov complexity
- Quantum information theory
Sessions
July 7: Organization. Recap of CS-683
- Basic organization, presentation assignments.
- Review of Information theory ideas
- Entropy, AEP, Compression and Capacity
Entropy of a random variable is given by
The capacity of a channel is defined by
Compression and Capacity determine the two fundamental information theoretic limits of data transmission,
- A review of Gaussain channels and their capacities.
- Let us take these analysis one step further. How much do you loose when you cross these barriers?
- We saw one situation when you try to transmit over the capacity. By Fano's inequality
- Rate distortion: A theory for lossy data compression.
References/Literature
- Elements of Information theory by Cover and Thomas.
July 14: Rate distortion theory - I
- Rate–distortion provides the theoretical foundations for lossy data compression.
- We try to find answer to the following question: Given an acceptable level of distortion, what is the minimal information that should be sent over a channel, so that the source can be reconstructed (up to that level of distortion) at the receiver?
- Quantization for a single random variable. Given a distribution for a random variable, what are the optimal choices for quantization? Answer is Lloyd's algorithm (closely related to k-means clustering).
- What about multiple random variables, treated at the same time? Even if the RVs are IID, quantizing them in sequences can result in better performance. (stated without proof).
- Define distortion D. When is a distortion pair (R,D) achievable?
- The rate distortion function R(D) is the min rate R such that (R,D) is achievable for a given D.
- There is also an information theoretic definition,
- We can show that both are equivalent.
- Proof follows closely the treatment on channel capacity.
July 21: Rate distortion theory - II
July 28: Network Information theory- I
Aug 04: Network Information theory- II
Aug 11: Wireless networks, cognitive radios
Aug 18: Multiple access channels, network coding techniques
a = 123343534534957349579347593475893475934875893475983457934785 + 923497239472394723947923742389