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