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

Krämer, Sebastian; Schneider, Reinhold; Grasedyck, Lars; Backmayr, Markus

doi:HT020464339

Tree tensor networks, associated singular values and high-dimensional approximation = Baum Tensor-Netzwerke, assoziierte Singulärwerte und hochdimensionale Approximation

Krämer, Sebastian^RWTH*

2020

Verantwortlichkeitsangabevorgelegt von Sebastian Krämer, M.Sc

ImpressumAachen 2020

Umfang1 Online-Ressource (xvi, 205 Seiten) : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2020

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grasedyck, Lars (Thesis advisor)^RWTH* ; Schneider, Reinhold (Thesis advisor) ; Backmayr, Markus (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2020-04-27

Online
DOI: 10.18154/RWTH-2020-05412
URL: https://publications.rwth-aachen.de/record/789753/files/789753.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
alternating least squares (frei) ; feasibility (frei) ; hierarchical Tucker format (frei) ; high-dimensional approximation (frei) ; honeycombs (frei) ; linear programming (frei) ; low-rank tensor formats (frei) ; quantum marginal problem (frei) ; rank adaption (frei) ; reweighted l1-minimization (frei) ; singular values (frei) ; tensor completion (frei) ; thin-plate splines (frei) ; tree tensor networks (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

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.

In this thesis, we develop an algebraic and graph theoretical reinterpretation of tensor networks and formats. We investigate properties of associated singular values and demonstrate their importance for high-dimensional approximation, in particular for model complexity adaption. This leads us to a concept of stability for iterative optimizations methods which we discuss at length for discrete matrix and tensor completion. We further generalize these ideas to the approximate interpolation of scattered data, and demonstrate the potential of the introduced algorithms on a data set that describes rolling press experiments. These largely algorithmic considerations are supplemented and supported by the theoretical examination of the interrelation between tensor singular values, and its relation to the quantum marginal problem. Tensor networks are essentially multilinear maps which reflect the connections between collections of tensors. In the first part, we discuss how two familiar concepts in mathematics yield an arithmetic that naturally describes such networks, and which formalizes the underlying, simple graph structures through universal assertions. The practicability of this calculus is reflected on by the straightforward implementations, which we provide also of well known algorithms. As a central theorem of this thesis serves the generalizing tree singular value decomposition, which, while not novel in its basic idea, incorporates various gauge conditions that stem from different, corresponding tensor formats. In the second part, we discuss details of high-dimensional, alternating least squares optimization in tree tensor networks, which are those families of tensors that form tree graphs. Due to the special properties of this class of formats, even high-dimensional problems can effectively be handled, in particular when the occurring, linear subproblems are solved via a conjugate gradient method. Subsequent to this introductory segment, we investigate the meaning of singular values in this context. As the model complexity is determined by the tensor ranks of the iterate, the proper calibration of such becomes essential in order to obtain reasonable solutions to recovery problems. Based on a specific definition of stability, we introduce and discuss modifications to standard alternating least squares as well as the relation to reweighted l1-minimization. We in particular demonstrate the use of these concepts for rank-adaptive algorithms. Such are further generalized from the discrete to the continuous setting, which we apply to the approximate interpolation of rolling press simulations. As the singular values associated to tensor networks stem from different matricizations of the same tensor, the question about the interrelation between such arises. In the third part we first show that the tensor feasibility problem is equivalent to a version of the quantum marginal problem. While the latter one has been well known in physics for multiple decades, the tensor version originating from mathematics has only recently been considered. We transfer several results into our setting and subsequently utilize the tree singular value decomposition in order to decouple high-dimensional feasibility problems into much simpler, smaller ones. Last but not least, we specifically consider this situation for the tensor train format, which leads us to cone theory, so-called honeycombs and the application of linear programming algorithms.

OpenAccess:
PDF
(additional files)