# Advanced topics in information theory

### From CYPHYNETS

**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.