Contributed talks on Tensors and Optimization
Mon 14:30–15:00, SW Raadzaal, Chair: Martijn BoussÃ©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.
- 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.
- 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.
- D. V. Savostyanov. Quasioptimality of maximum–volume cross interpolation of tensors. Linear Algebra Appl., 458:217–244, 2014.