Approximation of signals and functions in high dimensions with low dimensional structure: finite-valued sparse signals and generalized ridge functions
| dc.contributor.author | Keiper, Sandra | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Steidl, Gabriele | |
| dc.contributor.referee | Fornasier, Massimo | |
| dc.contributor.referee | Vybiral, Jan | |
| dc.date.accepted | 2020-10-01 | |
| dc.date.accessioned | 2020-10-27T16:18:55Z | |
| dc.date.available | 2020-10-27T16:18:55Z | |
| dc.date.issued | 2020 | |
| dc.description.abstract | In this thesis, we consider the class of high dimensional functions which contains functions which are defined in high-dimensional spaces but are known to be constant along some unknown manifolds. We study different reconstruction problems under additional assumptions. In the papers [54, 41, 56] (see Appendix A – C), we consider this problem in the context of compressed sensing and study the following problems. In Appendix A, [54], we assume that we aim to reconstruct a sparse and finite-valued vector. We present an approach that incorporates a finite values prior into basis pursuit, which is one classical reconstruction strategy in compressed sensing. In particular, we address unipolar binary and bipolar ternary sparse signals. We show that phase transition takes place earlier than using the classical basis pursuit approach and that, independently of the sparsity of the signal, at most N/2, respectively 3N/4, measurements are necessary to recover a unipolar binary, and a bipolar ternary signal uniquely. We further discuss robustness with respect to noisy measurements and generalizations to signals with entries in larger alphabets. In this work we consider Gaussian measurements. In Appendix B, [41], we concentrate on the recovery of sparse, (unipolar) binary signals through box-constrained basis pursuit. In contrast to the work in Appendix A we use biased measurement matrices, whose entries have a nonzero expected value. This enables us, using a probabilistic model, to provide conditions under which the recovery of both s-sparse and saturated binary signals is very likely. In fact, we also show that under the same conditions, the solution of the boxed-constrained basis pursuit program can be found using boxed-constrained least squares, which has some practical impact. This allows for example to establish stability without a-priori knowledge on the noise level. In Appendix C, [56], we also study the reconstruction of binary sparse signals from biased measurements. In contrast to the work in Appendix B, however, we consider biased partial random circulant instead of fully random measurements. We again show that the reconstruction via the least-squares strategy is as good as the reconstruction via the usually used program basis pursuit. We further show that we need as many measurements to recover an sparse signal as we need to recover a saturated signal. We further establish stability with respect to noisy measurements. Then, in [55],we study the approximation of generalized ridge functions, namely of functions which are constant along some submanifolds. We introduce the notion of linear-sleeve functions, whose function values only depend on the distance to some unknown linear subspace. We propose two effective algorithms to approximate linear-sleeve functions. We prove error bounds for both algorithms and provide an extensive numerical comparison of both. We further discuss an approach to apply these algorithms to capture general sleeve functions, which depend on the distance to some lower dimensional submanifold. | en |
| dc.description.abstract | In dieser Dissertation betrachten wir die Klasse von Funktionen, welche Funktionen enthält, die auf hochdimensionalen Räumen definiert aber konstant auf unbekannten Untermannigfaltigkeiten sind unter zusätzlichen Voraussetzungen untersuchen wir in diesem Zusammenhang unterschiedliche Rekonstruktionsprobleme. In den Veröffentlichungen [54, 41, 56] (siehe Appendix A – C) betrachten wir dieses Problem im Kontext des Compressed Sensings und untersuchen drei verschiedene Probleme. In [54] (siehe Appendix A), nehmen wir an, dass wir ein dünn besetztes Signal dessen Einträge aus einem endlichen Alphabet stammen rekonstruieren wollen. Wir präsentieren einen Ansatz zur Lösung des Problems, in welchem die Endlichkeit des Alphabets als Prior in die sogenannte l1-Minimierung, als Rekonstruktionsmethode, eingebaut wird. Die l1-Minimierung ist eine klassische Methode, die im Bereich des Compressed Sensing viel Anwendung findet. Insbesondere betrachten wir unipolare binäre und bipolar ternäre Signale. Wir zeigen, dass die sogenannte „Phase Transition“ früher stattfindet als bei der klassischen l1-Minimierung und dass, unabhängig von der dünnen Besetzung des Signals, N/2 beziehungsweise 3N/4 Messungen ausreichen, um ein unipolar binäres oder bipolar ternäres Signal eindeutig zu rekonstruieren. Darüber hinaus diskutieren wir die Robustheit des Algorithmus sowie Verallgemeinerungen auf Signale mit Einträgen aus größeren Alphabeten. In dieser Arbeit betrachten wir insbesondere Gauß-Messungen. In [41] (siehe Appendix B), konzentrieren wir uns auf die Rekonstruktion von dünn besetzen, (unipolar) binären Signalen mittels l1-Minimierungen unter sogenannten Box-Bedingungen, also der Bedingung, dass die Einträge des zu rekonstruierenden Signals in der Box [0, 1] liegen müssen. Im Gegensatz zu der Arbeit in Appendix A benutzen wir verschobene zufällige Messmatrizen, deren Einträge einen von Null verschieden Erwartungswert haben. Dies versetzt uns in die Lage, Bedingungen zu erarbeiten, unter denen die Rekonstruktion eines s-dünnen binären Signals genauso gut funktioniert, wie die Rekonstruktion eines (N-s)-dünnen, also unter Umständen dicht besetzten, binären Signals. Weiterhin zeigen wir sogar, dass unter denselben Bedingungen die Lösung der l1-Minimierung mit Box-Bedingungen genauso durch die Kleinste-Quadrate-Methode mit Box-Bedingungen gefunden werden kann. Das hat einige praktische Vorteile, da es uns beispielsweise erlaubt, Robustheit zu zeigen, ohne die Größenordnung der Störung vorher zu kennen. In [56] (siehe Appendix C), betrachten wir ebenso die Rekonstruktion von binären Signalen aus verschobenen zufälligen Messungen. Statt komplett randomisierter Matrizen betrachten wir nun randomisierte zyklische Matrizen. Dies ist für einige Anwendungen von Vorteil, da diese Matrizen unter anderem deutlich geringere Speicheranforderungen besitzen. Wir zeigen erneut, dass die Rekonstruktion mittels der Kleinste-Quadrate- Methode mit Box-Bedingungen genauso gut funktioniert wie die l1-Minimierung mit Box-Bedingungen. Darüber hinaus beweisen wir, dass man genauso viele Messungen benötigt, ein s-dünnes Signal zu rekonstruieren, wie ein (N -s)-dünnes (dicht besetztes) Signal. Weiterhin weisen wir Robustheit in Bezug auf gestörte Messungen nach. In [55] (siehe Appendix D) untersuchen wir die Approximation von verallgemeinerten Ridge Funktionen, genau genommen von Funktionen, die konstant entlang bestimmter Untermannigfaltigkeiten sind. Wir führen den Begriff der linearen-Sleeve Funktionen ein, deren Funktionswerte nur von der Distanz zu einem linearen Unterraum abhängen. Wir schlagen zwei effektive Algorithmen vor, um lineare-Sleeve Funktionen f (x) = g(dist(x, L)2) zu rekonstruieren. Weiterhin werden wir Fehlerschranken für beide Algorithmen beweisen und sie numerisch vergleichen. Am Ende werden wir noch eine Möglichkeit diskutieren, diese Ansätze auf noch allgemeinere Sleeve-Funktionen anzuwenden. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/11748 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-10636 | |
| 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 | finite alphabet | en |
| dc.subject.other | binary signals | en |
| dc.subject.other | ridge functions | en |
| dc.subject.other | function approximation | en |
| dc.subject.other | endliche Alphabete | de |
| dc.subject.other | binäre Signale | de |
| dc.subject.other | Ridge-Funktionen | de |
| dc.subject.other | Funktionen-Approximation | de |
| dc.title | Approximation of signals and functions in high dimensions with low dimensional structure: finite-valued sparse signals and generalized ridge functions | en |
| dc.title.translated | Approximation von Signalen und Funktionen in hohen Dimensionen mit niedrig-dimensionaler Struktur: endlich-wertige Signale und verallgemeinerte Ridge-Funktionen | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | domain | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Angewandte Funktionalanalysis | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.group | FG Angewandte Funktionalanalysis | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |