Compressive Sensing

Compressive Sensing (deutsche Übersetzung in etwa: 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 minimiere || x ||_0 unter  Ax=b   (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  minimiere || x ||_1 unter  Ax=b      (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.