Quasioptimality of maximum-volume cross interpolation of tensors

We consider a cross interpolation of high-dimensional arrays in the tensor train format. We prove that the maximum-volume choice of the interpolation sets provides the quasioptimal interpolation accuracy, that differs from the best possible accuracy by the factor which does not grow exponentially wi...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2014-10, Vol.458, p.217-244
Main Author: Savostyanov, Dmitry V.
Format: Article
Language:English
Subjects:
Cross interpolation
High-dimensional problems
Maximum-volume principle
Tensor train format
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a cross interpolation of high-dimensional arrays in the tensor train format. We prove that the maximum-volume choice of the interpolation sets provides the quasioptimal interpolation accuracy, that differs from the best possible accuracy by the factor which does not grow exponentially with dimension. For nested interpolation sets we prove the interpolation property and propose greedy cross interpolation algorithms. We justify the theoretical results and measure speed and accuracy of the proposed algorithm with numerical experiments.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2014.06.006