# Mathematics of Information

##### Offered in:

- Data Science Master: Information and Learning
- Doctoral and Post-Doctoral Studies: Department of Information Technology and Electrical Engineering
- Electrical Engineering and Information Technology Master: Recommended Subjects (Empfohlene Fächer)
- Mathematics Master: Selection: Further Realms (Auswahl: Weitere Gebiete)
- Physics Master: General Electives (Allgemeine Wahlfächer)
- Computational Science and Engineering Master: Electives (Wahlfächer)

Lecture: | Thursday, 9:15-12:00, ETZ E6 |

Discussion session: | Monday, 13:15-15:00, ML F 38 |

Instructor: | Prof. Dr. Helmut Bölcskei |

Teaching assistants: | Verner Vlačić, Dmytro Perekrestenko |

Office hours: | Wednesday, 13:00-14:00, ETF E 117 (Verner Vlačić) |

Tuesday, 13:00-14:00, ETF E 119 (Dmytro Perekrestenko) | |

Lecture notes: | Detailed lecture and exercise notes and problem sets with documented solutions will be made available as we go along. |

Credits: | 8 ECTS credits |

##### Course structure:

- The class will be taught in English. There will be a written exam in English of duration 180 minutes, which will contribute 75% towards the final grade.
- The remaining 25% will be awarded for student projects in the form of a group literature review. This project is a prerequisite for admission to the exam. Students should organize themselves in groups of 3 or 4 early in the semester and sign up via a doodle poll which will be made available here once the semester has started. Each group will be assigned a research paper on material relevant to the course, and given time until the end of the semester to understand the paper and summarize it in the form of a 20-minute presentation. Each student in a group should give a part of the presentation.
- Students will need to achieve a passing mark on the exam. The marks awarded for the presentation cannot be used to supplement an exam result that otherwise counts as a failure.

##### Exam structure:

- In the exam you will not be required to reproduce the proofs of abstract results and other complex arguments from discussion sessions, but you are required to know the theoretical concepts introduced. These include the various concepts from the general theory of Hilbert spaces such as orthonormal bases and projections, and concepts related to Gabor frames and wavelet bases, such as the Gabor frame operator, the Zak transform, multi-resolution analysis and FWT.
- Since this will be an open book exam, good familiarity with the concepts, their properties and mutual relations should be sufficient to tackle the exam well. You will not be asked to prove or derive anything from first principles without a hint to the relevant part of the coursework to be applied. Some problems may, in fairness, be inspired by coursework, so familiarising oneself with the details of both the lecture and the discussion session material may serve as a good exercise.
- On the other hand, there may of course be parts that rely on the application prerequisite material such as basic calculus, linear algebra, and the theory of signals and systems. Since the knowledge of such material is presupposed, these will not necessarily be accompanied by hints.

##### News

We will post important announcements, links, and other information here in the course of the semester, so please check back often! The first lecture will take place on Monday! 19 Feb, 13:00-16:00! in HG D7.2!, and the first discussion session will take place on Thursday 22 Feb, 10:00!-12:00 in HG E3!. The second exercise session will take place on Monday 26 Feb, 13:00-15:00 in HG G3. Starting from March 1st, the lectures and discussion sessions will take place as announced in the course catalogue. On May 3rd the class will take place 8:15-11:00! instead of 9:15-12:00, same room, i.e., ETZ E6.

##### Course Info

The class focuses on fundamental mathematical aspects of data sciences: Information theory (lossless and lossy compression), sampling theory, compressed sensing, dimensionality reduction, randomized algorithms for large-scale numerical linear algebra, approximation theory, neural networks as function approximators, mathematical foundations of deep learning.

**Signal representations:** Frames in finite-dimensional spaces, frames in Hilbert
spaces, wavelets, Gabor expansions

**Sampling theorems:** The sampling theorem as a frame expansion, irregular sampling,
multi-band sampling, density theorems, spectrum-blind sampling

**Sparse signals and compressed sensing:** Uncertainty
principles, recovery algorithms, Lasso, matching pursuits, compressed sensing, nonlinear
approximation, best k-term approximation, super-resolution

**High-dimensional data and dimensionality reduction:** Random
projections, the Johnson-Lindenstrauss Lemma, sketching

**Randomized algorithms for large-scale numerical linear algebra:** Large-scale matrix
computations, randomized algorithms for approximate matrix factorizations, matrix
sketching, fast algorithms for large-scale FFTs

**Information theory:** Entropy, mutual information, lossy compression,
rate-distortion theory, lossless compression, arithmetic coding, Lempel-Ziv compression

**Approximation theory:** Kolmogorov epsilon-entropy of signal classes, fundamental limits on compressibility of signal classes

**Mathematics of (deep) neural networks:** Universal function approximation with single-
and multi-layer networks, geometry of decision surfaces, convolutional
neural networks, scattering networks

##### Prerequisites

This course is aimed at students with a background in basic linear algebra, analysis,
and probability. We will, however, review required mathematical basics throughout
the semester in the discussion sessions.

##### Lecture and exercise notes

Here you can find the complete set of lecture notes for the course, as well as the notes taught in the discussion sessions.

- Lecture notes
- Harmonic Analysis of Deep Neural Networks

Presentation slides taught in lectures. - Hilbert Spaces

First chapter of the notes for the discussion sessions. - Gabor frames

Second chapter of the notes for the discussion sessions. - Wavelet frames

Third chapter of the notes for the discussion sessions. - Orthogonal Matching Pursuit

Fourth chapter of the notes for the discussion sessions.

##### Homework Assignments

There will be 6 homework assignments. You can hand in your solutions and get feedback from us, but it is not mandatory to turn in solutions. Complete solutions to the homework assignments will be posted on the course web page.

##### Homework Problem Sets

##### Handouts

##### Recommended reading

If you want to go into more depth or if you need additional background material, please check out these books:- T. Berger, "Rate distortion theory: A mathematical basis for data compression", Englewood Cliffs, NJ: Prentice Hall, 1971
- R. M. Gray, "Source coding theory", Boston, MA: Kluwer 1990
- T. Cover and J. Thomas, "Elements of information theory", 2nd ed., Wiley, 2006
- S. Mallat, "A wavelet tour of signal processing: The sparse way", 3rd ed., Elsevier, 2009
- M. Vetterli and J. Kovačević, "Wavelets and subband coding", Prentice Hall, 1995
- I. Daubechies, "Ten lectures on wavelets", SIAM, 1992
- O. Christensen, "An introduction to frames and Riesz bases", Birkhäuser, 2003
- K. Gröchenig, "Foundations of time-frequency analysis", Springer, 2001
- M. Elad, "Sparse and redundant representations — From theory to applications in signal and image processing", Springer, 2010
- M. Vetterli, J. Kovačević, and V. K. Goyal, "Foundations of signal processing", 3rd ed., Cambridge University Press, 2014
- S. Foucart and H. Rauhut, "A mathematical introduction to compressive sensing", Springer New York, 2013