EE477: Universal Schemes in Information Theory

Stanford University

Autumn Quarter 2004-05

Contents:

Announcements

[Tue, Sep 28] Classroom is changed to 200-030.
[Fri, Nov 5] Midterm is available here.
[Wed, Nov 24] Details on the final project are here.
[Wed, Dec 1] Project presentation schedule is here.

Lecture Notes

Lectures will use a combination of slides and board. These slides are not, and not meant to be, self-contained or "stand-alone". Some references in the slides can be found here.

Introduction and Overview [pdf] [4-up] (Updated: Sun, Sep 26 21:48:42)
Lossless Source Coding and the S-M-B Theorem [pdf] [4-up] (Updated: Sun, Sep 26 21:50:08)
The Lempel-Ziv Algorithms [pdf] [4-up] (Updated: Mon, Oct 04 01:02:18)
Lossy Source Coding [pdf] [4-up] (Updated: Mon, Oct 18 10:06:20)
Discrete Denoising [pdf] [4-up] (Updated: Sun, Oct 31 23:26:26)
Empirical Distribution of Rate-Constrained Codes and Compression-Based Denoising [pdf] [4-up] (Updated: Sun, Oct 31 23:26:26)

Basic Course Information

Lectures

200-030, MW 11-12:15pm, 3 Units.

Teaching staff

Instructor: Tsachy Weissman

Office: Packard 256

Tel: 736-1418

Email: tsachy@stanford.edu

Office hours: MW 1:30-2:30pm; or by appointment.

Teaching Assistant: Young-Han Kim

Office: Packard 251

Tel: 723-4544

Email: yhk@stanford.edu

Office hours: T 4-5pm, Packard 107; or by appointment.

Administrative Associate: Kelly Yilmaz

Office: Packard 259

Tel: 723-4539

Fax: 723-8473

Email: yilmaz@stanford.edu

Course Description

This is a graduate-level course focusing on universality issues in information theory. Problem areas will include compression (both lossless and lossy), prediction, denoising, filtering, and joint source-channel coding. Focus will be on characterization of the fundamentally optimum performance achievable in the respective settings, and on schemes that are guaranteed to universally attain that performance. Close connections between the problems will be highlighted. These allow to treat many of the problems within one unified framework. Topics include:

Lossless Coding: Entropy rate, Shannon-Mcmillan-Breiman theorem, Lempel-Ziv coding.
Lossy source coding: Rate distortion theory for stationary processes, Shannon lower bound, Yang-Kieffer codes.
Denoising: Fundamental limitations, DUDE (Discrete Universal DEnoiser).
Compression-based approach to denoising: Indirect Rate-Distortion coding, Occam Filters.
Prediction: Prediction of individual sequences. Minimax prediction. Prediction with expert advice. Incremental parsing predictor. Prediction in the presence of noise. Applications to sequential and limited-delay source coding and joint source-channel coding.
Filtering (causal denoising): Compound decision problem, Filtering as a prediction problem, sequential DUDE.

Prerequisites

Information theory (EE376A,B).
Probability and random processes at the level of EE278.
Knowledge of Matlab and/or C/C++ will be assumed for applied projects.

Textbook and Optional References

Material will be drawn from papers (comprehensive list will be given) as well as the following classical sources:

T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 1991.
I. Csiszar and J. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Akademiaki Kiado, 1981.
R. Gallager, Information Theory and Reliable Communication, Wiley, 1968.
T. Berger, Rate-Distortion Theory, Prentice-Hall, 1971.
R. M. Gray, Source Coding Theory, Kluwer, 1990.
R. M. Gray, Entropy and Information Theory, Springer-Verlag, 1990. (Available online.)

Auxiliary Texts:

R. M. Gray, Probability, Random Processes, and Ergodic Properties, Springer-Verlag, 1988. (Available online.)
L. Devroye, L. Gyorfi and G. Lugosi, A Probabilistic Theory of Pattern Recognition, Springer, 1996.
A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer, 1998.
L. Breiman, Probability, SIAM, 1992.
R. Durrett, Probability: Theory and Examples, Duxbury Press, 1996.
K. Petersen, Ergodic theory, Cambridge University Press, 1983.

Course Requirements

Homework assignments: 5-6 exercise sheets will be handed out at a decreasing frequency so as to leave more time for students to focus on their final projects as the quarter progresses.
Midterm: There will be a short take-home midterm exam, tentatively at the end of 7th week (November 6, 2004).
Final project: December 3 (Friday) will be the project presentation day (schedule). An approximately 20-minute project presentation will be given for each project. Including lunch and a few breaks, this should comfortably take us around 4 hours. We shall start at 11:00. Lunch will be provided. The project report is due December 10 (Friday).

Last updated: Wed Dec 1 22:01:26 2004