Webrelaunch 2020

Compressive Sensing (Sommersemester 2014)

Compressive Sensing (deutsche Übersetzung: komprimiertes Abtasten) bezeichnet ein sehr aktuelles Teilgebiet der Numerischen Linearen Algebra, in dem es darum geht, unterbestimmte lineare Systeme zu lösen. Dabei soll unter der Vielzahl von Lösungen diejenige gefunden werden, die die meisten Nullen enthält. Wir suchen also eine Lösung der Minimierungsaufgabe

$\min\{ || x ||_0: Ax=b\}, \qquad \qquad(1)$

wobei A eine Matrix ist, deren Spaltenzahl die Zeilenzahl deutlich übersteigt. Mit  || x ||_0 bezeichnen wir die Anzahl der Komponenten des Vektors x, die von Null verschieden sind. Da dieses Problem nicht in vernünftiger Rechenzeit gelöst werden kann (NP-schwer!), ersetzen wir es durch

$\min\{ || x ||_1: Ax=b\}, \qquad \qquad(2)$

worin die 1-Norm, || x ||_1=\sum_k |x_k|, verwendet wird. In der Vorlesung gehen wir u.a der Frage nach, ob eine Lösung von (2) auch das ursprüngliche Problem (1) löst und wir betrachten numerische Algorithmen, die (2) einer Lösung zuführen.

Die Anwendungen von Compressive Sensing sind vielfätig: Bild- und Mustererkennung, Fehlerkorrektur bei Informationübertragung, Signalabtastung, Datenanalyse etc.

Vorkenntnisse

Die Inhalte der Module „Analysis 1+2“, „Lineare Algebra 1+2“ werden benötigt. Basiswissen in Numerischer Mathematik und in Wahrscheinlichkeitstheorie ist hilfreich.

Termine
Vorlesung: Dienstag 9:45-11:15 Z 2 Beginn: 15.4.2014
Lehrende
Dozent Prof. Dr. Andreas Rieder
Sprechstunde: Montag, 14:00-15:00Uhr, und nach Vereinbarung
Zimmer 3.040 Kollegiengebäude Mathematik (20.30)
Email: andreas.rieder(at)kit.edu

Literaturhinweise