Tensor Trains Approximation Estimates in the Chebyshev Norm

Abstract

A new elementwise bound on the cross approximation error used for approximating multi-index arrays (tensors) in the format of a tensor train is obtained. The new bound is the first known error bound that differs from the best bound by a factor that depends only on the rank of the approximation \(r\) and on the dimensionality of the tensor \(d\), and the dependence on the dimensionality at a fixed rank has only the order \({{d}^{{{\text{const}}}}}\) rather than const^d. Thus, this bound justifies the use of the cross method even for high dimensional tensors.