EE5585 Data Compression (Spring 2013)

Instructor: Arya Mazumdar Email: arya@umn.edu

11:15 A.M. - 12:30 P.M. Tu,Th Keller Hall 3-125

Instructor availability: By appointment and after class.

No required textbook. The following references are useful.

References:

1. A. Gersho and R.M. Gray, Vector Quantization and Signal Compression, Springer.

2. T. Wiegand, H. Schwarz, Source Coding: Part I of Fundamentals of Source and Video Coding, Now.

3. T. Cover and J. Thomas, Elements of Information Theory, Wiley.

4. K. Sayood, Introduction to Data Compression, Morgan Kaufmann.

Grading Policy: Final Exam 40% + Midterm Exam* (1) 30% + Home Assignments (4) 20% + Scribe** (~2) 10%

*Exam date: Feb 26.

**Scribing template will be supplied.

Syllabus:

1. Preliminaries: Probability, Discrete Mathematics, Information Theory

2. Lossless coding: Source Coding Theory(Prefix-free and Universally Decodable Codes), Huffman Coding, Arithmetic Codes, The Lempel-Ziv Algorithm

3. Lossy Coding: Rate-distortion Theory, Scalar and Vector Quantization, Transform Coding Techniques, Subband Coding, Predictive Coding, Case Studies (JPEG/MPEG)

4. Compressed Sensing, Update/Query-efficient Compression.

Homeworks:

Homework 1 Homework 2 Homework 3 Homework 4

Lectures:

1. Jan 22 Scribe: Arya Mazumdar. Compressible data, Entropy, Source Coding, Kraft’s inequality. Notes.

2. Jan 24 Scribe: Trevor Webster. Uniquely decodable codes, Instantaneous codes, Shannon code. Notes.

3. Jan 29 Scribe: Katie Moenkhaus. Optimal Codes, Limit of compression, Huffman code, Optimality of Huffman code. Notes.

4. Jan 31 Scribe: John Havlik. Properties of entropy, Relative entropy, Arithmetic codes. Notes.

5. Feb 5 Scribe: Kriti Bhargava. Arithmetic coding, Typical sets, Lempel-Ziv coding. Notes.

6. Feb 7 Scribe: Joshua Krist. Optimality of Lempel-Ziv coding. Notes.

7. Feb 8 (Make up class for Feb 14) Scribe: Seth Hays. Optimality of Lempel-Ziv, continues. Notes.

8. Feb 12 Scribe: Viola Dsouza. What is information, Quantization, Covering codes, Volume of a Hamming sphere and asymptotics. Notes.

** Feb 14: No Class (Make up class Feb 8)

9. Feb 19 Scribe: Surya Ramachandran. Rate-distortion for binary source, Random coding, Worst-case vs. avg. case. Notes.

10. Feb 21 Scribe: Mandy Ding. Information measures, Rate-distortion Notes.

** Feb 26 Mid-Term Exam Problems

11. Feb 28 Scribe: Nanwei Yao. The rate-distortion converse theorem, Computation of R(D) function. Notes.

12. Mar 5 Scribe: Shreshtha Shukla. Continuous/mixed probability distribution, Gaussian random variable, Rate-distortion Notes.

** Mar 7 No Class (Make-up class Mar 8)

13. Mar 8 Scribe: Artem Mosesov. Scalar quantization, Optimal quantizer, Lloyd-Max algorithm. Notes.

14. Mar 12 Scribe: Cheng-Yu Hung. Non-uniform distributions, Lloyd algorithm, Vector quantization. Notes.

15. Mar 14 Scribe: Khem Chapagain. High-rate quantization, Shape-gain, Linde-Buzo-Gray. Notes.

******Spring Break******

16. Mar 26 Scribe: Fangying Zhang. Transform coding, Hadamard transform, Fix-free codes and Levenshtein et al. conjecture, Update-efficiency. Notes.

17. Mar 28 Scribe: Chendong Yang. Turing machine, Kolmogorov complexity. Notes.

18. Apr 2 Scribe: Shashanka Ubaru. Complexity of binary sequences, Incompressible sequences. Notes.

19. Apr 4 Scribe: Katie Moenkhaus. Complexity of a number, Karhunen-Loeve Transform, PCA, DFT/DCT. Notes.

20. Apr 9 Scribe: Aritra Konar. Compressed sensing, Vandermonde matrix, Stable recovery, Basis pursuit, Restricted Isometry. Notes.

21. Apr 11 Scribe: Zhongyu He. Proof: RIP is sufficient for stable recovery. Notes.

22. Apr 16 Scribe: Cheng Yu Hang. Matrices with RIP, Differential encoding. Notes.

23. Apr 18 Scribe: Trevor Webster. Differential Pulse Coded Modulation, Subband coding, Query efficiency. Notes.

24. Apr 23 Scribe: Yuanhang Wang. Introduction to Wavelets, Haar Wavelet, Lookback at Asymptotic Equipartition. Notes.

25. Apr 25 Scribe: Zhongyu He. More on Wavelets, The Philosophies of Data Compression. Notes.

26. Apr 30 The JPEG Standard. Handout.

27. May 2 Scribe: Fangying Zhang. Distributed Data Compression, Slepian-Wolf. Notes.

28. May 7 Scribe: Yijun Lin. Distributed Data Compression with Bernoulli Sources, Mod-2 Arithmatic, Pseudoinverse, Linear Codes. Notes.

29. May 9 Recap. Burrows-Wheeler. Handout (Last Class).