Quasioptimality of maximum-volume cross interpolation of tensors

Abstract

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 test the speed and accuracy of the proposed algorithm with convincing numerical experiments.

Submitted to SIAM J Matr Anal Appl

References in corpus (2)

• Alternating minimal energy methods for linear systems in higher dimensions. Part II: Faster algorithm and application to nonsymmetric systems
• Computation of extreme eigenvalues in higher dimensions using block tensor train format

Cited by in corpus (33)

• Computation of extreme eigenvalues in higher dimensions using block tensor train format
• Learning Feynman Diagrams with Tensor Trains
• Parallel cross interpolation for high-precision calculation of high-dimensional integrals
• Quantum Fourier Transform Has Small Entanglement
• Calculating vibrational spectra of molecules using tensor train decomposition
• Quantics Tensor Cross Interpolation for High-Resolution, Parsimonious Representations of Multivariate Functions in Physics and Beyond
• Learning tensor networks with tensor cross interpolation: new algorithms and libraries
• A Tensor Train Continuous Time Solver for Quantum Impurity Models
• Low-rank approximation in the numerical modeling of the Farley-Buneman instability in ionospheric plasma
• Opening the Black Box Inside Grover's Algorithm
• Iterative representing set selection for nested cross approximation
• Quantum State Tomography for Matrix Product Density Operators
• Efficient MPS representations and quantum circuits from the Fourier modes of classical image data
• Strong coupling impurity solver based on quantics tensor cross interpolation
• Tensor product approach to modelling epidemics on networks
• High Dimensional Uncertainty Quantification for an Electrothermal Field Problem using Stochastic Collocation on Sparse Grids and Tensor Train Decompositions
• Petz recovery versus matrix reconstruction
• Fast multidimensional convolution in low-rank formats via cross approximation
• Tensor Train Discrete Grid-Based Filters: Breaking the Curse of Dimensionality
• Direct interpolative construction of the discrete Fourier transform as a matrix product operator
• The State Preparation of Multivariate Normal Distributions using Tree Tensor Network
• Approximation in the extended functional tensor train format
• Tensor cross interpolation approach for quantum impurity problems based on the weak-coupling expansion
• Tensor train-Karhunen-Loève expansion for continuous-indexed random fields using higher-order cumulant functions
• Fully numerical Hartree-Fock calculations for atoms and small molecules with quantics tensor trains
• Preconditioners and Tensor Product Solvers for Optimal Control Problems from Chemotaxis
• Guaranteed a posteriori error bounds for low rank tensor approximate solutions
• Simulating Quantum Turbulence with Matrix Product States
• Typical Machine Learning Datasets as Low-Depth Quantum Circuits
• Low-Rank Kernel Matrix Approximation Using Skeletonized Interpolation With Endo- or Exo-Vertices
• Inchworm tensor train hybridization expansion quantum impurity solver
• Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques
• Tensorization of neural networks for improved privacy and interpretability