Mathematics of Information
- 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|
- 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.
- 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.
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.
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
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.
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.
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
- 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