ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

Contributed talks on Tensors and Optimization

Mon 14:30–15:00, SW Raadzaal, Chair: Martijn Boussé
Tensor–product algorithms for high–dimensional problems with uncertainty or noise
Dmitry Savostyanov (University of Brighton)

A variety of Monte Carlo techniques is rigorously studied and applied to almost every engineering problem involving some form of noise or uncertainty in the data. They sample a high–dimensional space of stochastic variables, choosing the positions for the samples randomly or quasi–randomly. The sampling strategy is often adapted to a certain class of problems, e.g. characterized by regularity of the solution, i.e. smoothness or decay rate w.r.t. stochastic variables.

As an alternative to this approach, the cross interpolation of tensors [3] has the following features:

  • the choice of samples is deterministic and adapted to a particular function;
  • the samples form one-dimensional lines in a high-dimensional space, that cross each other (hence the name);
  • due to the adaptivity, the position of lines are chosen subsequently;
  • the algorithm interpolates a given multivariate function in sampling poins by a tensor train model.

There are both theoretical [2] and experimental [1] evidence that tensor approximation converges faster than Monte-Carlo for certain stochastic PDEs.

In this talk we discuss a version of the cross interpolation algorithm for tensors, inspired by the maximum volume principle, proposed by Tyrtyshikov and colleagues, and successfully applied to matrices and 3-tensors. We present such an algorithm for high–dimensional tensors, demonstrate its fast convergence and efficiency for tensors arising from sPDEs. We also discuss challenges in development of a parallel version of this algorithms and the ways they can be overcomed.

  1. Jonas Ballani, Lars Grasedyck, and Melanie Kluge. A review on adaptive low-rank approximation techniques in the hierarchical tensor format. In Extraction of Quantifiable Information from Complex Systems, volume 102 of Lecture Notes in Computational Science and Engineering, pages 195–210. Springer, 2014.
  2. A. Kunoth and C. Schwab. Analytic regularity and GPC approximation for control problems constrained by linear parametric elliptic and parabolic PDEs. SIAM J Control and Optim., 51(3):2442–2471, 2013.
  3. D. V. Savostyanov. Quasioptimality of maximum–volume cross interpolation of tensors. Linear Algebra Appl., 458:217–244, 2014.