The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 2 of 284
Back to Result List

Optimization in Tensor Spaces for Data Science and Scientific Computing

  • In this thesis, we consider the solution of high-dimensional optimization problems with an underlying low-rank tensor structure. Due to the exponentially increasing computational complexity in the number of dimensions—the so-called curse of dimensionality—they present a considerable computational challenge and become infeasible even for moderate problem sizes. Multilinear algebra and tensor numerical methods have a wide range of applications in the fields of data science and scientific computing. Due to the typically large problem sizes in practical settings, efficient methods, which exploit low-rank structures, are essential. In this thesis, we consider an application each in both of these fields. Tensor completion, or imputation of unknown values in partially known multiway data is an important problem, which appears in statistics, mathematical imaging science and data science. Under the assumption of redundancy in the underlying data, this is a well-defined problem and methods of mathematical optimization can be applied to it. Due to the fact that tensors of fixed rank form a Riemannian submanifold of the ambient high-dimensional tensor space, Riemannian optimization is a natural framework for these problems, which is both mathematically rigorous and computationally efficient. We present a novel Riemannian trust-region scheme, which compares favourably with the state of the art on selected application cases and outperforms known methods on some test problems. Optimization problems governed by partial differential equations form an area of scientific computing which has applications in a variety of areas, ranging from physics to financial mathematics. Due to the inherent high dimensionality of optimization problems arising from discretized differential equations, these problems present computational challenges, especially in the case of three or more dimensions. An even more challenging class of optimization problems has operators of integral instead of differential type in the constraint. These operators are nonlocal, and therefore lead to large, dense discrete systems of equations. We present a novel solution method, based on separation of spatial dimensions and provably low-rank approximation of the nonlocal operator. Our approach allows the solution of multidimensional problems with a complexity which is only slightly larger than linear in the univariate grid size; this improves the state of the art for a particular test problem problem by at least two orders of magnitude.
  • In dieser Arbeit betrachten wir die Lösung hochdimensionaler Optimierungsprobleme, welchen eine Tensorstruktur niedrigen Ranges zugrunde liegt. Da die rechnerische Komplexität exponentiell mit der Anzahl der Dimensionen anwächst – dies wird als curse of dimensionality (”Fluch der Dimensionalität“) bezeichnet – stellen sie eine beträchtliche rechnerische Herausforderung dar und hören bereits für moderate Problemgrößen auf handhabbar zu sein. Multilineare Algebra und numerische Methoden für Tensoren haben eine Reihe von Anwendungen in den Gebieten von Data Science und des wissenschaftlichen Rechnens. Da praktische Probleme typischerweise eine hohe Dimension haben, sind effiziente Methoden, die Niedrigrangstrukturen ausnutzen, von essentieller Bedeutung. In dieser Arbeit betrachten wir jeweils eine Anwendung in diesen beiden Gebieten. Tensorvervollständigung, oder Imputation unbekannter Werte in teilweise bekannten mehrdimensionalen Datensätzen ist ein wichtiges Problem in der Statistik, der mathematischen Bildverarbeitung und in Data Science. Wenn man Redundanz der zugrundeliegenden Daten annimmt, ist es möglich, Verfahren der mathematischen Optimierung für dieses Problem anzuwenden. Da Tensoren festen Ranges eine Riemann’sche Mannigfaltigkeit des umgebenden hochdimensionalen Tensorraums darstellen, ist die Riemann’sche Optimierung der natürliche Rahmen für die Behandlung dieser Probleme, der sowohl mathematisch rigoros als auch rechnerisch effizient ist. Wir stellen ein neuartiges Riemann’sches Trust-Region-Verfahren vor, welches dem Vergleich mit dem neuesten Stand der Forschung für ausgewählte Anwendungen standhält sowie eine Verbesserung bekannter Methoden für einige Testprobleme bietet. Optimierungsprobleme mit partiellen Differentialgleichungen als Restriktion stellen ein Gebiet des wissenschaftlichen Rechnens dar, welches Anwendungen in zahlreichen Gebieten hat, von der Physik bis hin zur Finanzmathematik. Da Optimierungsprobleme, die von Differentialgleichungen herrühren, inhärent hohe Dimension haben, stellen diese Probleme eine rechnerische Herausforderung dar, insbesondere im Fall von drei oder mehr Dimensionen. Eine noch schwierigere Klasse von Problemen hat Operatoren vom Integral- statt vom Differentialtyp in der Restriktion. Diese Operatoren sind nicht-lokal und führen somit zu großen, vollbesetzten Gleichungssystemen. Wir präsentieren ein neuartiges Lösungsverfahren, welches auf der Trennung der Raumvariablen und auf einer Approximation für den lokalen Operator, welche beweisbar niedrigen Rang hat, basiert. Unser Ansatz erlaubt es, mehrdimensionale Probleme mit einer Komplexität zu lösen, die nur wenig höher als linear in der eindimensionalen Gitterweite ist; dies verbessert den Stand der Forschung für ein bestimmtes Testproblem um mindestens zwei Größenordnungen.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Gennadij Heidel
URN:urn:nbn:de:hbz:385-1-11079
DOI:https://doi.org/10.25353/ubtr-xxxx-77fe-6e9a
Referee:Volker Schulz, Jan Pablo Burgard, Boris N. Khoromskij
Advisor:Volker Schulz
Document Type:Doctoral Thesis
Language:English
Date of completion:2019/03/22
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2019/03/14
Release Date:2019/04/16
Tag:multilinear algebra; nonlinear optimization; numerical analysis; tensor methods
GND Keyword:Multilineare Algebra; Nichtlineare Optimierung; Numerische Mathematik
Number of pages:102
Institutes:Fachbereich 4
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoCC BY-NC-ND: Creative-Commons-Lizenz 4.0 International

$Rev: 13581 $