@phdthesis{Gay2014,
  type      = {Master Thesis},
  author    = {Matthias Gay},
  title     = {Compressed Sensing and Sparse Reconstruction Algorithms},
  url       = {https://nbn-resolving.org/urn:nbn:de:bsz:mit1-opus-38766},
  year      = {2014},
  abstract  = {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{\"u}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{\"u}r jeden d{\"u}nn besetzten Vektor mit der gleichen Anzahl von null verschiedener Elemente gleicherma{\"s}en funktionieren und auch nicht w{\"a}hrend des Prozesses auf bereits berechnete Projektionen zur{\"u}ckgreifen. Zum anderen geht es um die Rekonstruktion des d{\"u}nn besetzten Vektors aus diesen Projektionen, welche wesentlich weniger in der Zahl sind, als die Dimension des gesuchten Vektors. Das f{\"u}hrt auf ein unterbestimmtes lineares Gleichungssystem, das zun{\"a}chst unendlich viele L{\"o}sungen hat. Zusammen mit der Forderung der D{\"u}nnbesetztheit an die L{\"o}sung f{\"u}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{\"o}sen kann. Ziel dieser Arbeit ist es, einen einf{\"u}hrenden {\"U}berblick in das Sparse Reconstruction Problem zu geben und eine Auswahl wichtiger theoretischer Resultate zu pr{\"a}sentieren. Dabei wird zum einen die konvexe Relaxation des NP-schweren Problems betrachtet, welche mit Methoden der konvexen Optimierung effizient gel{\"o}st werden kann. Zum anderen werden schnelle Approximationsverfahren betrachtet, welche das kombinatorische Problem direkt approximativ l{\"o}sen. Dabei wird sich auf eine Auswahl beschr{\"a}nkt, die keinen Anspruch auf Vollst{\"a}ndigkeit erhebt, da es kurz nach Etablierung der Theorie eine wahre Explosion an Ver{\"o}ffentlichungen auf diesem Gebiet gab. Dennoch werden die wichtigsten Resultate und Ans{\"a}tze pr{\"a}sentiert und durch simulative Berechnungen best{\"a}tigt und illustriert, wobei die pr{\"a}sentierten Verfahren zum gro{\"s}en Teil selbst implementiert wurden.},
  language  = {de}
}