Universität zu Köln

Küng, Richard (2017). Convex reconstruction from structured measurements. PhD thesis, Universität zu Köln.

Preview

PDF kueng_convex_2017.pdf Download (33MB)

Abstract

Convex signal reconstruction is the art of solving ill-posed inverse problems via convex optimization. It is applicable to a great number of problems from engineering, signal analysis, quantum mechanics and many more. The most prominent example is compressed sensing, where one aims at reconstructing sparse vectors from an under-determined set of linear measurements. In many cases, one can prove rigorous performance guarantees for these convex algorithms. The combination of practical importance and theoretical tractability has directed a significant amount of attention to this young field of applied mathematics. However, rigorous proofs are usually only available for certain "generic cases"---for instance situations, where all measurements are represented by random Gaussian vectors. The focus of this thesis is to overcome this drawback by devising mathematical proof techniques can be applied to more "structured" measurements. Here, structure can have various meanings. E.g. it could refer to the type of measurements that occur in a given concrete application. Or, more abstractly, structure in the sense that a measurement ensemble is small and exhibits rich geometric features. The main focus of this thesis is phase retrieval: The problem of inferring phase information from amplitude measurements. This task is ubiquitous in, for instance, in crystallography, astronomy and diffraction imaging. Throughout this project, a series of increasingly better convex reconstruction guarantees have been established. On the one hand, we improved results for certain measurement models that mimic typical experimental setups in diffraction imaging. On the other hand, we identified spherical t-designs as a general purpose tool for the derandomization of data recovery schemes. Loosely speaking, a t-design is a finite configuration of vectors that is "evenly distributed" in the sense that it reproduces the first 2t moments of the uniform measure. Such configurations have been studied, for instance, in algebraic combinatorics, coding theory, and quantum information. We have shown that already spherical 4-designs allow for proving close-to-optimal convex reconstruction guarantees for phase retrieval. The success of this program depends on explicit constructions of spherical t-designs. In this regard, we have studied the design properties of stabilizer states. These are configurations of vectors that feature prominently in quantum information theory. Mathematically, they can be related to objects in discrete symplectic vector spaces---a structure we use heavily. We have shown that these vectors form a spherical 3-design and are, in some sense, close to a spherical 4-design. Putting these efforts together, we establish tight bounds on phase retrieval from stabilizer measurements. While working on the derandomization of phase retrieval, I obtained a number of results on other convex signal reconstruction problems. These include compressed sensing from anisotropic measurements, non-negative compressed sensing in the presence of noise and identifying improved convex regularizers for low rank matrix reconstruction. Going even further, the mathematical methods I used to tackle ill-posed inverse problems can be applied to a plethora of problems from quantum information theory. In particular, the causal structure behind Bell inequalities, new ways to compare experiments to fault-tolerance thresholds in quantum error correction, a novel benchmark for quantum state tomography via Bayesian estimation, and the task of distinguishing quantum states.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Konvexe Rekonstruktion von strukturierten Messungen German
Translated abstract:	Abstract Language Konvexe Signalrekonstruktion ist die Kunst des Lösens schlecht gestellter inverser Probleme mittels konvexer Optimierung. Sie ist auf eine große Anzahl von Problemen im Ingenieurwesen, der Signalanalyse, der Quantenmechanik und vielen weiteren anwendbar. Der bekannteste Anwendungsfall ist Compressed Sensing, dessen Ziel es ist, dünnbesetzte Vektoren aus einer unterbestimmten Menge an linearen Messungen zu rekonstruieren. In vielen Fällen ist es möglich, rigorose Leistungsgarantien für diese konvexen Algorithmen zu beweisen. Die Kombination aus praktischer Bedeutung und theoretischer Beweisbarkeit hat zu einem beträchtlichen Interesse an diesem jungen Teilgebiet der angewandten Mathematik geführt. Nichtsdestotrotz, sind rigorose mathematische Beweise für gewöhnlich nur für gewisse "generische Fälle" vorhanden---zum Beispiel Instanzen, wo alle Messungen zufälligen Gauss-Vektoren entsprechen. Das Thema dieser Arbeit ist es diese Beeinträchtigung durch das Entwickeln neuer mathematische Beweistechniken zu beheben, welche auf "strukturiertere" Messinstanzen anwendbar sind. Wohlgemerkt, kann Struktur hier mannigfaltig ausgelegt werden. Zum Beispiel könnte sie auf Messprozesse in konkreten Anwendungen hindeuten. Oder, abstrakter, Struktur im Sinne eines kleinen Messensembles, welches besondere geometrische Eigenschaften aufweist. Ein wichtiger Aspekt dieser Arbeit ist Phase Retrieval. Darunter versteht man die Aufgabe komplexe Phaseninformation aus Amplitudenmessungen zu gewinnen. Dieses Problem ist allgegenwärtig in vielen Disziplinen, zum Beispiel in Kristallographie, Astronomie und "Diffraction Imaging". Im Laufe dieses Projektes wurde eine Reihe stetig besser werdender konvexer Rekonstruktionsgarantien hergeleitet. Auf der einen Seite haben wir bestehende Resultate verbessert, welche für Messmodelle gelten die typische experimentelle Prozeduren in "Diffraction Imaging" imitieren. Auf der anderen Seite, haben wir sphärische t-Designs als Allzweck-Werkzeug für das Derandomisieren von Datenrekonstruktionsverfahren identifiziert. Vereinfacht gesagt, ist ein t-Design eine Konfiguration endlich vieler Vektoren, welches "gleichverteilt ist" in dem Sinn, dass sie die ersten 2t Momente der uniformen Verteilung auf der Sphäre reproduziert. Derartige Konfigurationen wurden zum Beispiel im Rahmen der algebraischen Kombinatorik, der Kodierungstheorie und in der Quanteninformationstheorie untersucht. Wir haben gezeigt, dass bereits sphärische 4-Designs es erlauben, beinahe optimale konvexe Rekonstruktionsgarantien für Phase Retrieval herzuleiten. Der Erfolg eines solchen Programms hängt stark von expliziten Konstruktionen sphärischer t-Designs ab. Um das zu erreichen, haben wir die Designeigenschaften von Stabilsatorzuständen untersucht. Diese sind eine in der Quanteninformationstheorie sehr wichtige Vektorkonfiguration. In mathematischer Hinsicht können sie mit diskreten symplektischen Vektorräumen in Verbindung gebracht werden---Eine Struktur die wir stark ausnützen. Wir haben gezeigt, dass diese Vektoren ein sphärisches 3-Design bilden, welche zudem einem 4-Design in gewisser Weise nahekommen. In dem wir diese Errungenschaften mit den Obengenannten verbinden, leiten wir optimale Schranken für Phase Retrieval mittels Stabilisatorzuständen her. Im Verlauf meiner Arbeit an der Derandomisierung von Phase Retrieval habe ich eine Anzahl an weiteren Resultaten im Rahmen der konvexen Signalanalyse erarbeitet. Diese beinhalten Compressed Sensing von anisotropen Messungen, verrauschtes nicht-negatives Compressed Sensing, und das Identifizieren eines besseren konvexen Regularisierers für bestimmte Matrixrekonstruktionsprobleme. Darüber hinaus, können die mathematischen Methoden, welche ich zum Bearbeiten schlecht-gestellter inverser Probleme verwendet habe, auf eine Vielzahl an Problemen der Quanteninformation angewendet werden. Konkret handelt es sich hierbei um die kausale Struktur hinter Bellungleichungen, neue Möglichkeiten Experimente mit dem "Fault-Tolerance Threshold" zu vergleichen, einen neuen Maßstab für Quantenzustandstomographie durch Bayes'sche Schätztheorie, und die Aufgabe Quantenzustände zu unterscheiden. German
Creators:	Creators Email ORCID ORCID Put Code Küng, Richard richard@kueng.at UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-77339
Date:	2017
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Physics > Institute for Theoretical Physics
Subjects:	Mathematics Physics
Uncontrolled Keywords:	Keywords Language convex optimization, signal analysis, complex projective designs, phase retrieval, quantum information theory English Konvexe Optimierung, Signalanalyse, komplexe projektive Designs, Phase Retrieval, Quanteninformationstheorie German
Date of oral exam:	13 December 2016
Referee:	Name Academic Title Gross, David Prof. Dr. Berg, Johannes Prof. Dr. Kutyniok, Gitta Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/7733