**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Riemannian Optimization for Solving High-Dimensional Problems with Low-Rank Tensor Structure

Abstract

In this thesis, we present a Riemannian framework for the solution of high-dimensional optimization problems with an underlying low-rank tensor structure. Here, the high-dimensionality refers to the size of the search space, while the cost function is scalar-valued. Such problems arise, for example, in the reconstruction of high-dimensional data sets and in the solution of parameter dependent partial differential equations. As the degrees of freedom grow exponentially with the number of dimensions, the so-called curse of dimensionality, directly solving the optimization problem is computationally unfeasible even for moderately high-dimensional problems. We constrain the optimization problem by assuming a low-rank tensor structure of the solution; drastically reducing the degrees of freedom. We reformulate this constrained optimization as an optimization problem on a manifold using the smooth embedded Riemannian manifold structure of the low-rank representations of the Tucker and tensor train formats. Exploiting this smooth structure, we derive efficient gradient-based optimization algorithms. In particular, we propose Riemannian conjugate gradient schemes for the solution of the tensor completion problem, where we aim to reconstruct a high-dimensional data set for which the vast majority of entries is unknown. For the solution of linear systems, we show how we can precondition the Riemannian gradient and leverage second-order information in an approximate Newton scheme. Finally, we describe a preconditioned alternating optimization scheme with subspace correction for the solution of high-dimensional symmetric eigenvalue problems.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications (5)

Loading

Loading

Loading

Related concepts (15)

Partial differential equation

In mathematics, a partial differential equation (PDE) is an equation which computes a function between various partial derivatives of a multivariable function.
The function is often thought of as

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions.
Optimization problems can be divided into two catego

Linear system

In systems theory, a linear system is a mathematical model of a system based on the use of a linear operator.
Linear systems typically exhibit features and properties that are much simpler than the n

We extend results on the dynamical low-rank approximation for the treatment of time-dependent matrices and tensors (Koch and Lubich; see [SIAM J. Matrix Anal. Appl., 29 (2007), pp. 434-454], [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2360-2375]) to the recently proposed hierarchical Tucker (HT) tensor format (Hackbusch and Kuhn; see [J. Fourier Anal. Appl., 15 (2009), pp. 706-722]) and the tensor train (TT) format (Oseledets; see [SIAM J. Sci. Comput., 33 (2011), pp. 2295-2317]), which are closely related to tensor decomposition methods used in quantum physics and chemistry. In this dynamical approximation approach, the time derivative of the tensor to be approximated is projected onto the time-dependent tangent space of the approximation manifold along the solution trajectory. This approach can be used to approximate the solutions to tensor differential equations in the HT or TT format and to compute updates in optimization algorithms within these reduced tensor formats. By deriving and analyzing the tangent space projector for the manifold of HT/TT tensors of fixed rank, we obtain curvature estimates, which allow us to obtain quasi-best approximation properties for the dynamical approximation, showing that the prospects and limitations of the ansatz are similar to those of the dynamical low rank approximation for matrices. Our results are exemplified by numerical experiments.

Michael Maximilian Steinlechner

Tensor completion aims to reconstruct a high-dimensional data set where the vast majority of entries is missing. The assumption of low-rank structure in the underlying original data allows us to cast the completion problem into an optimization problem restricted to the manifold of fixed-rank tensors. Elements of this smooth embedded submanifold can be efficiently represented in the tensor train or matrix product states format with storage complexity scaling linearly with the number of dimensions. We present a nonlinear conjugate gradient scheme within the framework of Riemannian optimization which exploits this favorable scaling. Numerical experiments and comparison to existing methods show the effectiveness of our approach for the approximation of multivariate functions. Finally, we show that our algorithm can obtain competitive reconstructions from uniform random sampling of few entries compared to adaptive sampling techniques such as cross-approximation.

,

The numerical solution of partial differential equations on high-dimensional domains gives rise to computationally challenging linear systems. When using standard discretization techniques, the size of the linear system grows exponentially with the number of dimensions, making the use of classic iterative solvers infeasible. During the last few years, low-rank tensor approaches have been developed that allow one to mitigate this curse of dimensionality by exploiting the underlying structure of the linear operator. In this work, we focus on tensors represented in the Tucker and tensor train formats. We propose two preconditioned gradient methods on the corresponding low-rank tensor manifolds: a Riemannian version of the preconditioned Richardson method as well as an approximate Newton scheme based on the Riemannian Hessian. For the latter, considerable attention is given to the efficient solution of the resulting Newton equation. In numerical experiments, we compare the efficiency of our Riemannian algorithms with other established tensor-based approaches such as a truncated preconditioned Richardson method and the alternating linear scheme. The results show that our approximate Riemannian Newton scheme is significantly faster in cases when the application of the linear operator is expensive.