Sparse recovery from Fourier measurements using compactly supported shearlets
| dc.contributor.advisor | Kutyniok, Gitta | |
| dc.contributor.author | Ma, Jackie Ken Yip | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Aldroubi, Akram | |
| dc.contributor.referee | Hansen, Anders | |
| dc.date.accepted | 2016-08-05 | |
| dc.date.accessioned | 2016-08-29T09:45:58Z | |
| dc.date.available | 2016-08-29T09:45:58Z | |
| dc.date.issued | 2016 | |
| dc.description.abstract | The main topic of this thesis is to study the sampling and reconstruction problem of signals that have a sparse structure. We thereby consider different models. First, we study the sampling and reconstruction problem using generalized sampling which is a linear reconstruction method that allows to use two arbitrary frames one as a sampling system and another one as a reconstruction system. The particular focus is then on using shearlets as a reconstruction system, since they provide the optimal sparse approximation rate for cartoon-like functions, which are compactly supported functions that are smooth up to a piecewise smooth discontinuity curve. As for the sampling process we often focus on the Fourier system, as these have a direct application to magnetic resonance imaging. In the context of shearlets, we also study the fundamental property of linear independence and present a novel construction of shearlets on bounded domains in this thesis. Further, we study the recovery of sparse signals by using l1-minimization which is at the heart of compressed sensing - a theory that studies the acquisition and recovery of sparse signals via an optimization problem from an incomplete amount of acquired data. This will be done in two ways: First, we investigate the infinite dimensional problem using multilevel sampling schemes as well as localized systems that carry an intrinsic multiscale structure such as shearlets. In fact, we will consider the more general case of alpha-molecules and show how recovery guarantees can be obtained for such systems in combination with Fourier samples. One focus will be on the balancing property which essentially determines the samples that must be acquired for successful recovery. It relates the sampling procedure to the sparsity structure of the system and we will show how it can be verified for certain type of systems such as alpha-shearlets. Next, we consider non-convex priors such as the lp-quasi norms for p in (0,1). We show theoretical stability of solutions that are obtained from lp-minimization when minimizing over dual coefficients as well as over primal coefficients. For the latter case we introduce a new concept called identifiability of duals which guarantees the sparsity equivalence between the primal and the dual system. The theoretical results are presented in full generality and apply to all sampling matrices that fulfill the restricted isometry property RIP. In some numerical experiments we will then compare the different solutions that are obtained by l1-minimization and lp-minimization, respectively, for the case of Fourier samples and shearlet reconstructions. We then also introduce a novel algorithm that is based on the multilevel structure of sparsifying transforms such as shearlets or wavelets. In particular, this structure is combined with the idea of reweighted l1-minimization. This algorithm is intensively tested and compared to other methods. Again the focus will be on Fourier measurements in these experiments. Finally, we apply shearlet based recovery to real data. First, we recover medical images from Fourier measurements as they appear in the applications. In fact, we will recover a 3D volume from radially subsampled k-space data. Furthermore, we also consider an inpainting problem appearing in electron microscopy. | en |
| dc.description.abstract | In dieser Arbeit studieren wir das Abtasten und die Rekonstruktion von Signalen, die eine dünnbesetzte Struktur besitzen. Wir werden dabei verschiedene Modelle betrachten. Zuerst studieren wir das Abtast- und Rekonstruktionsproblem mittels Generalized Sampling. Generalized Sampling ist eine lineare Rekonstruktionsmethode, die es erlaubt zwei beliebige Frames zu benutzen, einen für das Abtasten und den anderen für die Rekonstruktion. Ein wesentlicher Fokus wird in dieser Arbeit auf Shearlets liegen, welches ein Repräsentationssystem ist, das die sogenannte Optimal Sparse Approximation Rate für cartoon-ähnliche Funktionen erfüllt. Für das Abtastystem werden wir häufig die Fourierbasis betrachten, da diese auch in der Magnetresonanztomografie (MRT) verwendet wird. Unabhängig von dem Abtast- und Rekonstruktionsproblem mit Hilfe von Shearlets werden wir die fundamentale Eigenschaft der linearen Unabhängigkeit von Shearlets untersuchen und eine neue Konstruktion für Shearlets auf beschränkten Gebieten geben. Des Weiteren studieren wir die Rekonstrution von dünn besetzten Signalen durch l1-Minimierung was fundamental ist im Gebiet des Compressed Sensings -- eine Theorie, die die Akquisition und Rekonstruktion von dünnbesetzten Signalen durch lösen eines Optimierungsproblems anhand von einer unvollständigen Menge an Messungen studiert. Dabei werden wir zwei verschiedene Situationen studieren: Zunächst untersuchen wir das unendlich dimensionale Problem mit Hilfe von multiskalen Abtaststrategien und lokalisierten Rekonstruktionssystemen, welche wiederum mit einer natürlichen Multiskalenstruktur versehen sind, wie zum Beispiel die Shearletsysteme. Insbesondere werden wir eine Verallgemeinerung der Shearlets betrachten, nämlich das der Alpha-Moleküle. Wir zeigen, dass eine stabile Rekonstruktion von Fouriermessungen für solche Systeme möglich ist, dabei werden wir insbesondere die Balancing Property untersuchen, die im Wesentlichen das Abtastschema unter Berücksichtigung der Struktur des Rekonstruktionssystems bestimmt und zeigen, wie man diese für Systeme wie Alpha-Shearlets nachweisen kann. Anschließend studieren wir nicht-konvexes Compresses Sensing in dem wir über lp-quasinormen für p aus (0,1) minimieren. Wir zeigen die Stabilität der Lösungen die man durch eine derartige Minimierung über Primal Frame Coefficients oder über Dual Frame Coefficients erhält. Für Letzteres führen wir ein neues Konzept ein, das der sogenannten Frames mit identifizierbaren dualen Frames. Die Resultate hierzu werden in größerer Allgemeinheit bewiesen und sind anwendbar auf alle Abtastmatrizen, die die sogenannte Restricted Isometry Property erfüllen. In einigen zusätzlichen numerischen Experimenten vergleichen wir dann Rekonstruktionen, die durch lp-quasinormen erhalten wurden, mit Rekonstruktionen die durch klassisches Compressed Sensing, erhalten worden sind, d.h. durch Minimierung über die l1-Norm. Diese Experimente sind dann für Shearletrekonstruktionen anhand von Fouriermessungen durchgeführt worden. Wir werden außerdem einen neuen Algorithmus vorstellen der auf der Multiskalenstruktur der sparsifizierenden Transformen beruht, wie zum Beispiel die Shearlet- oder Wavelettransformation. Insbesondere wird diese Stuktur mit reweighted l1-minimization kombiniert. Wir testen den Algorithmus an diversen Bildern, in dem von einigen Fouriermessungen der jeweiligen Bilder, Shearletrekonstruktionen berechnen werden. Darüberhinaus werden wir in dieser Arbeit Shearlets auf reale Daten anwenden. Als erstes rekonstruieren wir medizinische Daten anhand von Fouriermessungen, die von einem MRT-Gerät aufgenommen worden sind. Insbesondere rekonstruieren wir ein 3D Volumen anhand eines radial abgetasteten k-Raums. Anschließend betrachten wir ein Inpainting Problem aus der Elektronenmikroskopie. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/5855 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-5454 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 518 Numerische Analysis | de |
| dc.subject.ddc | 519 Wahrscheinlichkeiten, angewandte Mathematik | de |
| dc.subject.other | sampling | en |
| dc.subject.other | Fourier measurements | en |
| dc.subject.other | shearlets | en |
| dc.subject.other | compressed sensing | en |
| dc.subject.other | frames | en |
| dc.title | Sparse recovery from Fourier measurements using compactly supported shearlets | en |
| dc.title.translated | Sparse-Rekonstruktionen von Fourier-Messungen mit Hilfe von Shearlets mit kompaktem Träger | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |