227-0434-10L  Mathematics of Information

SemesterFrühjahrssemester 2019
DozierendeH. Bölcskei
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheEnglisch


KurzbeschreibungThe class focuses on fundamental aspects of mathematical information science: Frame theory, sampling theory, sparsity, compressed sensing, uncertainty relations, spectrum-blind sampling, dimensionality reduction and sketching, randomized algorithms for large-scale sparse FFTs, inverse problems, (Kolmogorov) approximation theory, and information theory (lossless and lossy compression).
LernzielAfter attending this lecture, participating in the exercise sessions, and working on the homework problem sets, students will have acquired a working knowledge of the most commonly used mathematical theories in information science. Students will also have to carry out a research project, either individually or in groups, with presentations at the end of the semester.
Inhalt1. Signal representations: Frames in finite-dimensional spaces, frames in Hilbert spaces, wavelets, Gabor expansions

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

3. Sparsity and compressed sensing: Uncertainty relations in sparse signal recovery, recovery algorithms, Lasso, matching pursuit algorithms, compressed sensing, super-resolution

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

5. Randomized algorithms for large-scale sparse FFTs

6. Approximation theory: Fundamental limits on compressibility of signal classes, Kolmogorov epsilon-entropy of signal classes, optimal encoding and decoding of signal classes

7. Information theory: Entropy, mutual information, lossy compression, rate-distortion theory, lossless compression, arithmetic coding, Lempel-Ziv compression
SkriptDetailed lecture notes will be provided at the beginning of the semester.
Voraussetzungen / BesonderesThis 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 exercise sessions.