Quasioptimality of maximum-volume cross interpolation of tensors

Dmitry Savostyanov

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)217-244
Number of pages28
JournalLinear Algebra and its Applications
Publication statusPublished - 24 Jun 2014


  • High-dimensional problems
  • Tensor train format
  • Maximum-volume principle
  • Cross interpolation


Dive into the research topics of 'Quasioptimality of maximum-volume cross interpolation of tensors'. Together they form a unique fingerprint.

Cite this