EE 477: Universal Schemes in Information Theory

Stanford University

Fall 2009-2010

Announcements

Additional References
A. Gupta, S. Verdu, T. Weissman, "Rate-Distortion in Near-Linear Time"
A new lossy compression website
The first lecture is on Tue., Sep. 22nd.
A short movie from lossy source coding has been uploaded. After the first lecture, you will know exactly what it means.

Course Description

How can information be processed, stored, or predicted efficiently? How can noise be removed or reduced from it? What is the minimum amount to be stored so that it can be recovered within a specified fidelity ? Recent decades have witnessed a fruitful interplay of ideas from information theory, statistics, probability and theoretical computer science which resulted in universal schemes: algorithms that perform such tasks essentially optimally, with no knowledge of statistical properties of the data. Several of these algorithms have practical and graceful implementations, and are of wide current use. The course will focus on theoretical and algorithmic aspects of universal schemes. Emphasis will be placed on identifying common themes and on developing tools for constructing and for analyzing the performance of such schemes in a unified framework. These tools will be put to use and applied to new problems in the final project.

A tentative syllabus can be found here.

Prerequisites:

Information theory EE376A

References:

Material will be drawn from the current literature, papers in Link 1, Link 2 and Link 3, and from 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.)
R. M. Gray, Probability, Random Processes, and Ergodic Properties, Springer-Verlag, 1988.
L. Devroye, L. Gyorfi and G. Lugosi, A Probabilistic Theory of Pattern Recognition, Springer, 1996.
N. Cesa-Bianchi and G Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.
Luc Devroye, A course in density estimation, Boston: Birkhauser, 1987.
L. Devroye and G. Lugosi, Combinatorial Methods in Density Estimation, Springer, 2001.
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. The 4th edition is online
K. Petersen, Ergodic theory, Cambridge University Press, 1983.
M. Mézard, and A. Montanari, Information, Physics, and Computation, Oxford University Press, Oxford 2009. Link

Course Info

Times and Location:

GESB 134, Tue&Th 11-12:15pm, 3 Units Email:

Please use ee477-aut0910-staff@lists.stanford.edu for any question related to the course.

Teaching staff:

Instructor: Tsachy Weissman

Office: Packard 256

Tel: 736-1418

Email: tsachy *AT* stanford.edu

Office hours: Thursday 1:30pm -- 3:30pm

Teaching Assistant: Lei Zhao

Office: Packard 251

Tel: 723-4544

Email: leiz *AT* stanford.edu

Office hours: Friday 10:00am -- 12:00pm Packard 251

Administrative Associate: Kelly Yilmaz

Office: Packard 259

Tel: 723-4539

Email: yilmaz *AT* stanford.edu

Course Requirement

Grading will be based on homework sets (30%) (approximately biweekly), lecture scribe and participation (30%), and a project (40%) .
The project presentation day is set to be Thu. Dec., 3rd. The due day to submit the final project report is Fri., Dec. 11th.

Last modified: