Course 048703, Spring 2008:
Noise Removal - An Information Theoretic View
Here are the dates for the 12 lectures (all taking place 16:30-18:30), including the class locations:
– Lecture 1: Monday, May 19 Slides of introductory lecture
– Lecture 2: Sunday, May 25, room 354 (scribing by Oren Zeitlin)
– Lecture 3: Monday, May 26, room 351
– Lecture 4: Sunday, June 1, *room 1007*
– Lecture 5: Monday, June 2, room 351
– Lecture 6: *Tuesday*, June 10, room 354 (note that Sunday and Monday of that week are vacation days due to Shavuot and Tuesday will be a Sunday format)
– Lecture 7: Sunday, June 15, room 354 (scribing by Renata Goldman)
– Lecture 8: Monday, June 16, room 351
– Lecture 9: Sunday, June 22, room 354
– Lecture 10: Monday, June 23, room 351
– Lecture 11: Sunday, June 29, room 354
– Lecture 12: Monday, June 30, room 351
• Staff details:
– Lecturer: Tsachy Weissman, email: email@example.com, phone: 4732
Office hours: Thursdays 13:30-14:30 and 15:30-16:30, or by coordination
– T.A.: We might get one eventually
– Material will be drawn primarily from papers in
with particular focus on papers in
– Background reading may occasionally be recommended from the following classical sources:
o T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley, 1991.
o I. Csiszar and J. Korner, Information Theory: Coding Theorems for DiscreteMemoryless Systems, Akademiaki Kiado, 1981.
o R. Gallager, Information Theory and Reliable Communication, Wiley, 1968.
o T. Berger, Rate-Distortion Theory, Prentice-Hall, 1971. R. M. Gray, SourceCoding Theory, Kluwer, 1990.
o R. M. Gray, Entropy and Information Theory, Springer-Verlag, 1990. (Available online.)
o R. M. Gray, Probability, Random Processes, and Ergodic Properties, Springer-Verlag, 1988.
o L. Devroye, L. Gyorfi and G. Lugosi, A Probabilistic Theory of Pattern Recognition, Springer, 1996.
o N. Cesa-Bianchi and G Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.
o Luc Devroye, A course in density estimation, Boston: Birkhauser, 1987.
o L. Devroye and G. Lugosi, Combinatorial Methods in Density Estimation, Springer, 2001.
o A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Springer, 1998.
o L. Breiman, Probability, SIAM, 1992.
o R. Durrett, Probability: Theory and Examples, Duxbury Press, 1996.
o K. Petersen, Ergodic theory, Cambridge University Press, 1983.
• Course requirements:
50% Lecture report: Each enrolled student will be assigned a 2-hour lecture to scribe. The write-up should be an expansion rather than a summary of the lecture, elaborating where needed on issues that have been merely skimmed over, filling in mathematical details that were skipped, etc.
1. Report should be prepared in English in Latex
2. Report will be due 2 weeks after the lecture
3. I will give you some feedback on the report 2 weeks after you submit it
4. 2 weeks after you receive my feedback, the final version of the report will be due
5. Final grade on report will be the average of your grades on versions of steps 2 and 4
50% Exercise sheet: As we go through the material, during the lectures, we will pose problems, questions and exercises every once in a while. These will be collected into an exercise sheet that will be handed out before the end of the semester. You will be required to choose a subset of the questions (the size of which will be specified), to be completed independently (no teamwork) and handed in at a date that will be specified, some time after the end of the semester.
• Course Description:
– Introduction and overview [1 lecture]
– Discrete Denoising [3 lectures]:
o Fundamental performance limits
o Optimal but non-universal schemes:
§ Bayes-optimal schemes
§ Example: forward-backward recursions for noise-corrupted Markov processes
o Universal denoising
§ Discrete Universal DEnoiser (DUDE): construction and performance analysis
§ Variants of DUDE
§ Performance boosts for the non-asymptotic regime
§ Theory and algorithms for non-stationary data
– Compression-based denoising [2.5 lectures]:
o Lossy compression preliminaries:
§ Rate distortion theory for ergodic processes
§ Shannon lower bound
§ Empirical distribution of rate distortion codes
§ Universal lossy source coding:
1. Yang-Kieffer codes
2. Lossy compression via Markov chain Monte Carlo
o Indirect rate distortion theory
o Universal denoising via lossy compression
– Denoising of analogue data (via approaches developed in the discrete case) [2 lectures]:
o (a bit about) Wavelet thresholding techniques (pros and cons)
o Universal denoising:
§ Kernel density estimation-based techniques
§ Context quantization-based techniques
– Sequential decision making in the presence of noise [2.5 lectures]:
o Noise-free case:
§ prediction with expert advice
§ lossless coding preliminaries
§ prediction via compression
§ Ziv-Lempel (LZ) predictor
o Noisy prediction
o Filtering (sequential estimation):
§ compound sequential decision problem
§ filtering via prediction
§ LZ filtering
– Applications [remaining time]:
o Image denoising
o Data compression and communications:
§ lossy source coding with decoder side information (the Wyner-Ziv problem)
§ decoding of systematically encoded redundant data
[time permitting; probably not this short semester:]
Suggestions and/or requests for specific topics will be welcome