On some aspects of recovery of sparse signals in high dimensions from nonlinear measurements using compressed sensing
| dc.contributor.advisor | Kutyniok, Gitta | |
| dc.contributor.advisor | Vybiral, Jan | |
| dc.contributor.author | Kolleck, Anton | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Kutyniok, Gitta | |
| dc.contributor.referee | Rauhut, Holger | |
| dc.contributor.referee | Vybiral, Jan | |
| dc.date.accepted | 2017-03-24 | |
| dc.date.accessioned | 2017-04-07T07:42:15Z | |
| dc.date.available | 2017-04-07T07:42:15Z | |
| dc.date.issued | 2017 | |
| dc.description.abstract | In data processing we often aim for the recovery of signals in very high dimensions from linear measurements. In many applications such as medical imaging, it turns out that the signal of interest is sparse (or allows a sparse representation in a certain dictionary), i.e., most of its entries are zero or at least very small. Some ten years ago, compressed sensing emerged as a novel method for the recovery of sparse signals in high dimensions, where the sparsity assumption is used to heavily reduce the needed number of linear measurements. In the first main part of this thesis we deal with the theory of s-numbers. Our main interest is the so-called Carl’s inequality, which estimates the asymptotic behavior of important instances of s-numbers such as the Gelfand numbers. The main result in this part is given by Carl’s inequality for Gelfand numbers on quasi-Banach spaces. In particular, in the context of compressed sensing Carl’s inequality can be used to estimate the minimal needed number of linear measurements in order to obtain reasonable approximations of a sparse signal. The basic setting of compressed sensing deals with the recovery of sparse signals from linear measurements. However, many applications gain only access to nonlinear measurements. Thus, in the remaining part of this thesis we discuss specific nonlinearities in the measurement process. More precisely, first we will discuss the problem of 1-bit compressed sensing, where we only obtain the signs of the linear measurements. Although getting less information from the measurement process, it is still possible to recover the signal (up to some scalar multiple) from the same amount of linear measurements as in the usual compressed sensing setting. Recently, several algorithms where proposed to solve the 1-bit compressed sensing problem. We will analyze the so called l1-support vector machines, which are often used in machine learning applications. After discussing the 1-bit compressed sensing problem, we will discuss the approximation of ridge functions, which we can interpret in the following two ways. On the one hand, in the context of compressed sensing we can interpret the approximation of ridge function as a generalization of the 1-bit compressed sensing problem. Instead of the sign, here the measurements get disturbed by some unknown nonlinearity. However, in the theory of ridge functions we usually assume a differentiability condition on the nonlinearity, which is obviously not fulfilled for the sign function. On the other hand, we observe that the approximation of multivariate functions in high dimensions often suffers from the curse of dimensionality. It turns out that even the approximation of arbitrarily often differentiable multivariate functions is intractable in general. Hence, if we still want to approximate multivariate functions in high dimensions, we have to assume further structure. One of the probably simplest structures we can think of is given by ridge functions, which are constant along hyperplanes. | en |
| dc.description.abstract | Im Bereich der Datenverarbeitung stehen wir oft vor dem Problem, ein hochdimensionales Signal aus linearen Messungen rekonstruieren zu müssen. Dabei stellen wir in vielen Anwendungen, wie der bildgebenden Diagnostik (engl: medical imaging) in der Medizin, fest, dass die Signale oft dünnbesetzt (engl.: sparse) sind, d.h., dass die meisten Einträge des Signals null oder zumindest sehr klein sind. Vor ungefähr zehn Jahren hat sich Compressed Sensing als neuartige Methode zur Rekonstruktion von dünnbesetzten Signalen aus linearen Messungen hervorgetan. In dem ersten Abschnitt dieser Dissertation beschäftigen wir uns mit der Theorie der s-Zahlen (engl.: s-numbers). Unser Hauptaugenmerkt liegt hierbei auf der Ungleichung von Carl, welche das asymptotische Verhalten einiger wichtiger s-Zahlen abschätzt. Das Hauptresultat in diesem Abschnitt ist ein Beweis der Ungleichung von Carl für den Fall von Gelfand Zahlen auf quasi-Banach Räumen. Im Kontext von Compressed Sensing können wir dieses Resultat dann insbesondere nutzen, um eine Schranke für die Mindestanzahl an benötigten linearen Messungen herzuleiten, aus welchen wir dünnbesetzte Signale zufriedenstellend rekonstruieren können. Das Ausgangsproblem von Compressed Sensing beschäftigt sich mit der Rekonstruktion von Signalen aus linearen Messungen. In vielen Anwendungen erhalten wir allerdings nur Zugang zu nichtlinearen Messungen, mit welchen wir uns in den weiteren Abschnitten der Arbeit befassen. Zunächst betrachten wir das Problem des sogenannten 1-Bit Compressed Sensing. Hier erhalten wir lediglich die Vorzeichen der linearen Messungen und dadurch sehr viel weniger Informationen als im klassischen Compressed Sensing. Dennoch ist es möglich, das Signal (bis auf ein skalares Vielfaches) mit der gleichen Ordnung an Messungen zu rekonstruieren. Um das Problem des 1-Bit Compressed Sensing zu lösen, wurden bereits einige Rekonstruktionsalgorithmen vorgeschlagen. Wir werden uns dabei auf die l1-Support Vector Machines beschränken, welche häufig eine Anwendung bei Problemen des Maschinellen Lernens (engl.: Machine Learning) finden. Nachdem wir das Problem des 1-Bit Compressed Sensing besprochen haben, widmen wir uns der Approximation von Ridge Funktionen. Diese können wir auf zwei verschiedene Arten interpretieren: Auf der einen Seite, im Kontext von Compressed Sensing, können die Ridge Funktionen als Verallgemeinerung des 1-Bit Compressed Sensing Problems verstanden werden. Anstelle der Vorzeichen der Messwerte erhalten wir hier eine beliebige, unbekannte nichtlineare Störung der Messwerte. Dabei ist allerdings zu bemerken, dass wir bei der Approximation von Ridge Funktionen die zusätzliche Annahme treffen, dass die Nichtlinearität differenzierbar ist und somit das Vorzeichen der Messwerte hier nicht als Nichtlinearität gewählt werden kann. Auf der anderen Seite bemerken wir, dass die Approximation von Funktionen in vielen Veränderlichen oft unter dem Fluch der Dimensionalität leidet. Bemerkenswert ist, dass selbst die gleichmäßige Approximation von beliebig oft differenzierbaren Funktionen unter diesem Fluch leidet. Da wir aber dennoch an der Approximation von Funktionen in vielen Veränderlichen interessiert sind, müssen wir weitere strukturelle Annahmen treffen. Eine der einfachsten dieser Annahmen ist die der Ridge Funktionen, nämlich, dass die Funktionen konstant entlang von Hyperebenen sind. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/6269 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-5828 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | de |
| dc.subject.other | compressed sensing | en |
| dc.subject.other | Carl's inequality | en |
| dc.subject.other | support vector machines | en |
| dc.subject.other | ridge functions | en |
| dc.title | On some aspects of recovery of sparse signals in high dimensions from nonlinear measurements using compressed sensing | en |
| dc.title.translated | Rekonstruktion von dünnbesetzten Signalen in hohen Dimensionen aus nichtlinearen Messungen durch Compressed Sensing | en |
| 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 |