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

#### Basic information:

Lecture: | Thursday, 9:15-12:00, live broadcast on the ETH video portal. The first lecture takes place on Thursday 03 March 2022, 9:15-12:00. |

Exercise session: | Monday, 14:15-16:00, live broadcast on the ETH video portal. The first exercise session takes place on Monday 28 Feb. 2022, 14:15-16:00. |

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

Teaching assistants: | Thomas Allard, Clemens Hutter |

Office hours: | Monday, 16:15-17:15, via Zoom. Please contact the TAs for their Zoom IDs. |

Lecture notes: | Detailed lecture notes can be found below in the section 'Lecture notes and prerequisite material'. Exercise problem sets along with detailed solutions will be made availble as we go along, see the section 'Exercise sessions'. The access information for the notes will be sent by email to all students registered for the class. |

Credits: | 8 ECTS credits |

#### Lecture Recordings:

The recordings of the lectures will be available the next day on the ETH video portal.#### Course structure

- The class will be taught in English. There will be a written exam in English of duration 180 minutes.

#### News

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

There will be no lecture and no exercise session in the first week of the semester. The class will start with the exercise session on Feb. 28th, 2022. During the first week of the semester, the students are kindly asked to watch the videos from last year's lecture starting from 25.2.2021 at 30:00 until 11.03.2021 at 00:39. The videos can be found under the following link or in the table below.

#### 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, super-resolution, spectrum-blind sampling, subspace algorithms (ESPRIT), estimation in the high-dimensional noisy case, Lasso**Dimensionality reduction:**Random projections, the Johnson-Lindenstrauss Lemma- Mathematics of Learning:
**Approximation theory:**Linear and nonlinear approximation, best M-term approximation, greedy algorithms, fundamental limits on compressibility of signal classes, Kolmogorov-Tikhomirov epsilon-entropy of signal classes, optimal compression of signal classes**Uniform laws of large numbers:**Rademacher complexity, Vapnik-Chervonenkis dimension, classes with polynomial discrimination

H. Bölcskei and A. Bandeira

#### 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 notes and prerequisite material

- Lecture notes
- Prerequisite material

Hilbert spaces - Handouts

Comprehensive summary of linear algebra

Comprehensive summary of functional analysis

Notes on compact sets

#### Recordings and handwritten notes

Date | Recording Lectures | Handwritten Notes | Recording Exercises |
---|---|---|---|

03.03.2022 | Lecture 1 | iPad notes | Exercise 1 |

10.03.2022 | Lecture 2 | iPad notes | Exercise 2 |

17.03.2022 | Lecture 3 | iPad notes | Exercise 3 |

24.03.2022 | Lecture 4 | iPad notes V2 | Exercise 4 |

31.03.2022 | Lecture 5 | iPad notes | Exercise 5 |

07.04.2022 | Lecture 6 | iPad notes | Exercise 6 |

14.04.2022 | Lecture 7 | iPad notes | Exercise 7 |

28.04.2022 | Lecture 8 | iPad notes | no exercise |

05.05.2022 | Part 1, from 24:41 Part 2, until 44:30 |
iPad notes | Exercise 9 |

12.05.2022 | Lecture 10 | iPad notes | Exercise 10 |

19.05.2022 | Lecture 11 | iPad notes | Exercise 11 |

02.06.2022 | Lecture 12 | iPad notes | Exercise 12 |

#### Recordings from 2021

#### Homework Assignments

There will be exercise session notes posted every Thursday after the lecture. The TAs will inform you by email which of the problems in these notes will be solved in the exercise session the following Monday. The expectation is that you prepare these problems before the exercise session.

#### Exercise sessions

28.02.2022 | Set 1 | Solutions 1 | Complements on the Fourier Transform |

07.03.2022 | Set 2 | Solutions 2 | |

14.03.2022 | Set 3 | Solutions 3 | Complements on Wavelets |

21.03.2022 | Set 4 | Solutions 4 | |

28.03.2022 | Set 5 | Solutions 5 | |

04.04.2022 | Set 6 | Solutions 6 | |

11.04.2022 | Set 7 | Solutions 7 | |

02.05.2022 | Set 8 | Solutions 8 | |

09.05.2022 | Set 9 | Solutions 9 | Notes on compact sets |

16.05.2022 | Set 10 | Solutions 10 | |

23.05.2022 | Set 11 | Solutions 11 | |

30.05.2022 | Set 12 | Solutions 12 | Complements on ULLN and Rademacher Complexity |

#### Previous years' exams and solutions

Year | Exam | Handout | Solutions |
---|---|---|---|

Summer 2018 | Exam 2018 | - | Solutions 2018 |

Summer 2019 | Exam 2019 | Handout 2019 | Solutions 2019 |

Summer 2020 | Exam 2020 | Handout 2020 | Solutions 2020 |

Winter 2020/2021 | Exam 2020/2021 | Handout 2020/2021 | Solutions 2020/2021 |

Summer 2021 | Exam 2021 | Handout 2021 | Solutions 2021 |

Winter 2021/2022 | Exam 2021/2022 | Handout 2021/2022 | Solutions 2021/2022 |

Summer 2022 | Exam 2022 | Handout 2022 | Solutions 2022 |

#### Material for the exam

All the material that has been covered during the lectures and the exercise sessions will be relevant for the exam.

You are allowed to bring 10 handwritten or printed A4 pages summary (or 5 A4 pages on both sides). Electronic devices (laptops, calculators, cellphones, etc...) are not allowed.

#### Recommended reading

If you want to go into more depth or if you need additional background material, please check out these books:

- 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
- M. J. Wainwright, "High-dimensional statistics: A non-asymptotic viewpoint", Vol. 48, Cambridge University Press, 2019
- R. Vershynin, "High-dimensional probability: An introduction with applications in data science", Vol. 47, Cambridge University Press, 2018