Matthias Gay

• Die vorliegende Arbeit befasst sich mit einem relativ jungen Gebiet innerhalb der angewandten Mathematik, dem Compressed Sensing. Darin geht es zum einen um die Frage, wie man einen dünn besetzten, hochdimensionalen Vektor durch lineare Projektionen in seiner Dimension reduzieren kann, ohne dass dabei Information verloren geht. Dieses "Sensing"-Verfahren ist nicht-adaptiv, d.h. es soll für jeden dünn besetzten Vektor mit der gleichen Anzahl von null verschiedener Elemente gleichermaßen funktionieren und auch nicht während des Prozesses auf bereits berechnete Projektionen zurückgreifen. Zum anderen geht es um die Rekonstruktion des dünn besetzten Vektors aus diesen Projektionen, welche wesentlich weniger in der Zahl sind, als die Dimension des gesuchten Vektors. Das führt auf ein unterbestimmtes lineares Gleichungssystem, das zunächst unendlich viele Lösungen hat. Zusammen mit der Forderung der Dünnbesetztheit an die Lösung führt dies auf ein NP-schweres kombinatorisches Optimierungsproblem. Die Theorie von Compressed Sensing bietet nun Antworten auf die Fragen, wann dieses Problem l¨osbar ist und wie man es mit effizienten Verfahren der Optimierung praktisch lösen kann. Ziel dieser Arbeit ist es, einen einführenden Überblick in das Sparse Reconstruction Problem zu geben und eine Auswahl wichtiger theoretischer Resultate zu präsentieren. Dabei wird zum einen die konvexe Relaxation des NP-schweren Problems betrachtet, welche mit Methoden der konvexen Optimierung effizient gelöst werden kann. Zum anderen werden schnelle Approximationsverfahren betrachtet, welche das kombinatorische Problem direkt approximativ lösen. Dabei wird sich auf eine Auswahl beschränkt, die keinen Anspruch auf Vollständigkeit erhebt, da es kurz nach Etablierung der Theorie eine wahre Explosion an Veröffentlichungen auf diesem Gebiet gab. Dennoch werden die wichtigsten Resultate und Ansätze präsentiert und durch simulative Berechnungen bestätigt und illustriert, wobei die präsentierten Verfahren zum großen Teil selbst implementiert wurden.