# 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: Core subjects (Kernfächer), Specialization courses (Vertiefungsfächer), Advanced core courses
- Mathematics Master: Selection: Further Realms (Auswahl: Weitere Gebiete)
- Physics Master: General Electives (Allgemeine Wahlfächer)
- Quantum Engineering Master: Electives (Wahlfächer)
- Computational Science and Engineering Master: Electives (Wahlfächer)
- Statistics Master: Statistical and Mathematical Courses (Statistische und mathematische Fächer)

Lecture: | Thursday, 9:15-12:00, ETZ E6. The first two lectures take place on Monday 24 Feb 2020, 13:15-15:00, ML E 12, and on Thursday 27 Feb 2020, 9:15-12:00, ETZ E6. |

Discussion session: | Monday, 13:15-15:00, ML E 12. The first discussion session takes place on Monday 2 Mar 2020, 13:15-15:00. |

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

Teaching assistants: | Verner Vlačić, Thomas Allard |

Office hours: | Monday, 15:15-16:15, ETF E 117 and ETF E 118 |

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.
- Admission to the exam is contingent on the successful completion of a literature review project or a computational project. The research project can be carried out either individually or in groups of up to 4. The project consists of either 1. software development for the solution of a practical signal processing or machine learning problem or 2. the analysis of a research paper or 3. a theoretical research problem of suitable complexity. Students are welcome to propose their own project at the beginning of the semester. The outcomes of all projects have to be presented to the entire class at the end of the semester.

##### News

We will post important announcements, links, and other information here in the course of the semester, so please check back often!

##### Updates related to COVID-19

Both the lecture and the exercise session will be recorded from week to week and the recordings will be made available at the latest the day after the exercise (i.e. Tuesday) or lecture (i.e. Friday) by noon under the following link.

As the lecture will not be live-streamed, Prof. Dr. Helmut Bölcskei will offer a Skype or Zoom office hour every Monday 16:15-17:15. If you want to talk to him, please send an email to hboelcskei@ethz.ch before so he can communicate his Skype or Zoom id to you.

Thomas Allard and Verner Vlačić will hold their office hours via skype or zoom as well and at the regular time, i.e., Monday 15:15-16:15. If you want to talk to them, please email them so they can send you their Skype or Zoom accounts.

The compulsory research project is on. Information on how to sign up will follow.

Homeworks will be posted as planned and you may scan your solutions and email them to Verner Vlačić and Thomas Allard.

##### Course Info

The class focuses on mathematical aspects of information science and learning theory.

Mathematics of Information:

**Signal representations:** Frame theory, wavelets, Gabor expansions, sampling theorems, density theorems

**Sparsity and compressed sensing:** Sparse linear models, uncertainty relations in sparse signal recovery, matching pursuits, super-resolution, spectrum-blind sampling, subspace algorithms (MUSIC, ESPRIT, matrix pencil), estimation in the high-dimensional noisy case, LASSO

**Dimensionality reduction:** Random projections, the Johnson-Lindenstrauss Lemma

Mathematics of Learning:

**Approximation theory:** Nonlinear approximation theory, fundamental limits on compressibility of signal classes, Kolmogorov-Tikhomirov epsilon-entropy of signal classes, optimal compression of signal classes, recovery from incomplete data, information-based complexity, curse of dimensionality

**Uniform laws of large numbers:** Rademacher complexity, Vapnik-Chervonenkis dimension, classes with polynomial discrimination, blessings of dimensionality

##### Material to study for the exam

Here is the material that you need to prepare for the exam:

- Compressive sensing (Sections 3.1-3.4 in the lecture notes and the corresponding discussion sessions),
- Approximation theory (Chapter 10 in the lecture notes),
- Sparsity in redundant dictionaries (Chapter 11 in the lecture notes),
- Theorem 12.10 and Proposition 12.11 in the lecture notes and their proofs (the proof of the bounded differences inequality and the corresponding results about martingales are not required),
- VC dimension (Sections 12.5-12.6 in the lecture notes).

##### Prerequisites

This course is aimed at students with a background in linear algebra, probability, and basic functional analysis. In particular, familiarity with Hilbert spaces is expected on the level of the "Hilbert spaces" chapter posted below (excluding the appendices).

##### Lecture and exercise notes

Here we will post lecture and discussion session notes in due course.

- Lecture notes
- Hilbert spaces

Prerequisite material. - Discussion sessions introduction

Introductory chapter for the discussion sessions. - Fourier transform

First chapter of the notes for the discussion sessions. - Orthonormal wavelets

Second chapter of the notes for the discussion sessions. - Compressive sensing

Third chapter of the notes for the discussion sessions. - Metric entropy of Lipschitz function classes

Fourth chapter of the notes for the discussion sessions. - Uniform Laws of Large Numbers

Fifth chapter of the notes for the discussion sessions.

##### Lecture and exercise video recordings

Here we will post lecture and discussion session videos. Both the lecture and the exercise session will be recorded from week to week and the recordings will be made available at the latest the day after the exercise (i.e. Tuesday) or lecture (i.e. Friday) by noon.

##### 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

##### Previous years' exams and solutions

##### 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, 2013