Geometrical Interpretations and Algorithmic Verification of Exact Solutions in Compressed Sensing
In an era dominated by the topic big data, in which everyone is confronted with spying scandals, personalized advertising, and retention of data, it is not surprising that a topic as compressed sensing is of such a great interest. Further the field of compressed sensing is very interesting for problems in signal- and image processing. Similarly, the question arises how many measurements are necessarily required to capture and represent high-resolution signal or objects. In the thesis at hand, the applicability of three of the most applied optimization problems with linear restrictions in compressed sensing is studied. These are basis pursuit, analysis l1-minimization und isotropic total variation minimization. Unique solutions of basis pursuit and analysis l1-minimization are considered and, on the basis of their characterizations, methods are designed which verify whether a given vector can be reconstructed exactly by basis pursuit or analysis l1-minimization. Further, a method is developed which guarantees that a given vector is the unique solution of isotropic total variation minimization. In addition, results on experiments for all three methods are presented where the linear restrictions are given as a random matrix and as a matrix which models the measurement process in computed tomography. Furthermore, in the present thesis geometrical interpretations are presented. By considering the theory of convex polytopes, three geometrical objects are examined and placed within the context of compressed sensing. The result is a comprehensive study of the geometry of basis pursuit which contains many new insights to necessary geometrical conditions for unique solutions and an explicit number of equivalence classes of unique solutions. The number of these equivalence classes itself is strongly related to the number of unique solutions of basis pursuit for an arbitrary matrix. In addition, the question is addressed for which linear restrictions do exist the most unique solutions of basis pursuit. For this purpose, upper bounds are developed and explicit restrictions are given under which the most vectors can be reconstructed via basis pursuit.
In Zeiten von Big Data, in denen man nahezu täglich mit Überwachungsskandalen, personalisierter Werbung und Vorratsdatenspeicherung konfrontiert wird, ist es kein Wunder dass ein Forschungsgebiet wie Compressed Sensing von so grossem Interesse ist. Es stellt sich die Frage, wie viele Messungen tatsächlich nötig sind, um ein Signal oder ein Objekt hochaufgelöst darstellen zu können. In der vorliegenden Arbeit wird die Anwendungsmöglichkeit von drei in Compressed Sensing verwendeten Optimierungsprobleme mit linearen Nebenbedingungen untersucht. Hierbei handelt es sich namentlich um Basis Pursuit, Analysis l1-Minimierung und Isotropic Total Variation. Es werden eindeutige Lösungen von Basis Pursuit und der Analysis l1-Minimierung betrachtet, um auf der Grundlage ihrer Charakterisierungen Methoden vorzustellen, die Verifizieren ob ein gegebener Vektor exakt durch Basis Pursuit oder der Analysis l1-Minimierung rekonstruiert werden kann. Für Isotropic Total Variation werden hinreichende Bedingungen aufgestellt, die garantieren, dass ein gegebener Vektor die eindeutige Lösung von Isotropic Total Variation ist. Darüber hinaus werden Ergebnisse zu Experimenten mit Zufallsmatrizen als linearen Nebenbedingungen sowie Ergebnisse zu Experimenten mit Matrizen vorgestellt, die den Aufnahmeprozess bei Computertomographie simulieren. Weiterhin werden in der vorliegenden Arbeit verschiedene geometrische Interpretationen von Basis Pursuit vorgestellt. Unter Verwendung der konvexen Polytop-Theorie werden drei unterschiedliche geometrische Objekte untersucht und in den Zusammenhang mit Compressed Sensing gestellt. Das Ergebnis ist eine umfangreiche Studie der Geometrie von Basis Pursuit mit vielen neuen Einblicken in notwendige geometrische Bedingungen für eindeutige Lösungen und in die explizite Anzahl von Äquivalenzklassen eindeutiger Lösungen. Darüber hinaus wird der Frage nachgegangen, unter welchen linearen Nebenbedingungen die meisten eindeutigen Lösungen existieren. Zu diesem Zweck werden obere Schranken entwickelt, sowie explizite Nebenbedingungen genannt unter denen die meisten Vektoren exakt rekonstruiert werden können.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved