Tree tensor networks, associated singular values and high-dimensional approximation

• Baum Tensor-Netzwerke, assoziierte Singulärwerte und hochdimensionale Approximation

Krämer, Sebastian; Grasedyck, Lars (Thesis advisor); Schneider, Reinhold (Thesis advisor); Backmayr, Markus (Thesis advisor)

Aachen (2020)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

In dieser Arbeit entwickeln wir eine algebraische und graphentheoretische Neuinterpretation von Tensor-Netzwerken und Formaten. Wir untersuchen die Eigenschaften der zugehörigen Singulärwerte und deren Bedeutung für hochdimensionale Approximation, insbesondere hinsichtlich der Anpassung der Modellkomplexität. Dies führt uns zu einem Konzept der Stabilität für iterative Optimierungsverfahren, welches wir ausführlich anhand von diskreter Matrix- und Tensorvervollständigung diskutieren. Ferner verallgemeinern wir diese Ideen bis hin zur approximativen Lösung von nicht gleichmäßig strukturierten Datensätzen und demonstrieren das Potential der vorgestellten Algorithmen anhand von einem Datensatz der Walzvorgänge beschreibt. Diese weitgehend algorithmischen Überlegungen werden ergänzt und unterstützt durch die theoretische Untersuchung des Zusammenhangs zwischen Tensor-Singulärwerten und dem so genannten quantum marginal problem. Tensor-Netzwerke sind im Wesentlichen multilineare Abbildungen, die die Zusammenhänge innerhalb von Mengen von Tensoren darstellen. Im ersten Teil diskutieren wir, wie zwei grundlegende und vertraute mathematische Konzepte eine Arithmetik ergeben, die solche Netzwerke auf natürliche Art beschreibt, und welche die zugrunde liegenden, einfachen graphentheoretischen Strukturen durch universelle Aussagen formalisiert. Die Praktikabilität dieser Konzepte spiegelt sich in den einfachen Implementierungen wider, die auch für bekannte Algorithmen behandelt werden. Als zentrales Theorem dieser Arbeit dient die verallgemeinernde Baum-Singulärwertzerlegung, die, obwohl nicht neu in ihrer Grundidee, verschiedene Normalisierungsbedingungen von bestimmten Tensor-Formaten vereint. Im zweiten Teil werden Details der hochdimensionalen, alternierenden Optimierung der kleinsten Quadrate in Baum-Tensor-Netzwerken diskutiert, die gerade solche Familien von Tensoren sind, welche kreisfreie Graphen bilden. Aufgrund der besonderen Eigenschaften dieser Klasse von Formaten können auch hochdimensionale Probleme effektiv gelöst werden, insbesondere wenn die auftretenden, linearen Teilprobleme mit einem Verfahren der konjugierten Gradienten gelöst werden. Im Anschluss zu diesem einführenden Abschnitt untersuchen wir die Bedeutung der Singulärwerte in diesem Kontext. Da die Modellkomplexität durch die Tensorränge bestimmt wird, wird deren richtige Kalibrierung unerlässlich um korrekte Lösungen für Rekonstruktionsprobleme zu erhalten. Basierend auf einer bestimmten Definition der Stabilität führen wir Modifikationen für die gewöhnliche, alternierende Optimierung der kleinsten Quadrate ein und diskutieren diese, sowie deren Beziehung zu l1-Minimierung. Wir demonstrieren insbesondere den Nutzen dieser Konzepte für Rang adaptive Algorithmen. Jene werden weiter vom diskreten zum kontinuierlichen Fall verallgemeinert, welchen wir auf die approximative Interpolation von simulierten Walzvorgängen anwenden. Da die Singulärwerte, die aus den Tensor-Netzwerken hervorgehen, von unterschiedlichen Matrifizierungen desselben Tensors stammen, stellt sich die Frage nach dem Zusammenhang zwischen diesen. Im dritten Teil zeigen wir zunächst, dass das Problem der Realisierbarkeit von Singulärwerten einer Version des quantum marginal problem entspricht. Während letzteres in der Physik seit mehreren Jahrzehnten bekannt ist, wird die Variante, die aus der Mathematik hervorgeht, erst seit recht kurzer Zeit untersucht. Wir übertragen verschiedenen Ergebnisse in unseren Sachverhalt und nutzen die Baum-Singulärwertezerlegung um dazugehörige, hochdimensionale Probleme in deutlich einfachere und kleinere zu entkoppeln. Schlussendlich betrachten wir insbesondere die Situation für das tensor train Format, was uns zur Theorie über Kegel, sogenannten honeycombs sowie der Anwendungen linearer Programmierung führt.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl für Angewandte Mathematik und Institut für Geometrie und Praktische Mathematik [111410]