Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4763
Main Title: Geometric compressed sensing and structured sparsity
Translated Title: Geometrisches Compressed Sensing und strukturierte Sparsity
Author(s): Bojarovska, Irena S.
Advisor(s): Kutyniok, Gitta
Referee(s): Fickus, Matthew
Pfander, Götz
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Compressed Sensing ist eine neuartige Methode in der Datenverarbeitung, welche einen Vorteil aus der Tatsache zieht, dass viele Signale dünnbesetzt (engl.: sparse) sind oder zumindest eine dünnbesetzte Darstellung erlauben. Das heißt, dass nur eine kleine Anzahl an Einträgen des Signals von null verschieden sind, oder dass sich das Signal als Linearkombination weniger Elemente eines gegebenen Erzeugendensystems darstellen lässt. Die Dünnbesetztheit erlaubt dann die Rekonstruktion des Signals aus signifikant weniger Messungen im Vergleich zu traditionellen Methoden. Im ersten Teil dieser Dissertation betrachten wir Signale mit einer gewissen geometrischen Struktur. Genauer betrachten wir Signale, welche sich als Vereinigung weniger diskreter Geraden darstellen lassen. Wir untersuchen die Frameeigenschaften des Systems aus diskreten Geraden und wenden Compressed Sensing-Methoden an, um u.a. diskrete Geraden von Punkten zu trennen. Zudem betrachten wir Signale, welche dünnbesetzt bzgl. eines diskreten Gaborsystems sind. Dabei sind wir besonders an Gaborsystemen interessiert, welche von sogenannten Differenzmengen generiert werden. Diese können wiederum als Geraden in einem endlichdimensionalen projektiven Raum betrachtet werden. Wir werden zeigen, dass die Gaborsysteme als optimal dünnbesetzte Fusion Frames gesehen werden können, und es sich zudem um äquidistante tight Fusions Frames handelt, also um optimale Grassmannsche Packungen. In der zweiten Hälfte der Dissertation betrachten wir die Phasenrückgewinnung (engl.: phase retrieval) von Signalen. Im Gegensatz zum Compressed Sensing, welches sich mit der Rückgewinnung von Signalen aus linearen Messungen beschäftigt, rekonstruieren wir die Signale bei der Phasenrückgewinnung nur aus den Beträgen der entsprechenden Messungen. Im Allgemeinen müssen die Signale hier nicht notwendigerweise dünnbesetzt sein, wobei das Interesse an dieser zusätzlichen Annahme in den letzten Jahren gestiegen ist, um die nötige Anzahl der Messungen zu reduzieren. Daher werden wir uns hier genauer mit Signalen beschäftigen, welche dünnbesetzt bzgl. eines beliebigen, aber festen Erzeugendensystems sind. Schließlich betrachten wir die Phasenrückgewinnung aus Messungen mit einem diskreten Gaborsystem, welches durch einen geeignet gewählten Vektor generiert wird, und beweisen, dass die Phasenrückgewinnung so garantiert werden kann. Für dünnbesetzte Signale können wir die Anzahl der Messungen signifikant reduzieren. Weiter diskutieren wir, welche Generatoren für das Gaborsystem geeignet sind und stellen einen Algorithmus zur Lösung des Problems auf.
Compressed sensing is a novel methodology in data processing, which takes an advantage of the fact that most signals are sparse (have a small number of nonzeros), or admit a sparse representation, i.e., can be represented as a linear combination of few elements of a given frame (dictionary). Sparsity then allows one to recover the signal from considerably fewer linear measurements than what is required by traditional methods. In the first part of the thesis, we exploit sparse geometric structure of the signal. We consider signals consisting of unions of a few discrete lines as the simplest case of geometric sparsity. We investigate the frame properties of the system of discrete lines and the application of compressed sensing to such signal models, for example, for separating discrete lines and points. The second type of structured sparsity that we consider is, signals which are sparse in a dictionary of time- and frequency-shifts, i.e., a Gabor system. We are interested in Gabor systems generated by difference sets, which can be seen as lines in finite projective geometry. We further view this system as a fusion frame, show that it is optimally sparse, and moreover an equidistant tight fusion frame, i.e. it is an optimal Grassmannian packing. In the second half of this thesis, we move from compressed sensing to phase retrieval: if compressed sensing studies the recovery of signals from a set of linear, non-adaptive measurements, phase retrieval tries to recover signals from only the absolute values of those measurements. In general, the signal in the phase retrieval problem is not necessarily sparse, but there has been an increased interest in the recent years in including the sparsity assumption for this problem, and by that lowering the number of measurements needed for recovery of the signal. We investigate the case when the signal itself is not sparse, but it has a sparse representation in an arbitrary dictionary. Finally, we consider the phase retrieval problem in the case when the measurements are time- and frequency-shifts of a suitably chosen generator. We prove an injectivity condition for recovery of any signal from all time-frequency shifts, and for recovery of sparse signals, when only some of those measurements are given. We discuss which generators are suitable for sparse phase retrieval from Gabor measurements, and provide an algorithm for solving this problem.
URI: urn:nbn:de:kobv:83-opus4-72986
http://depositonce.tu-berlin.de/handle/11303/5060
http://dx.doi.org/10.14279/depositonce-4763
Exam Date: 25-Sep-2015
Issue Date: 4-Nov-2015
Date Available: 4-Nov-2015
DDC Class: 510 Mathematik
Subject(s): Frametheorie
Phasenrückgewinnung
Gaborsysteme
Signalverarbeitung
Compressed sensing
frame theory
phase retrieval
Gabor systems
signal processing
Creative Commons License: https://creativecommons.org/licenses/by/3.0/de/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
bojarovska_irena.pdf2.09 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.