TT-cross approximation for multidimensional arrays

As is well known, a rank-r matrix can be recovered from a cross of r linearly independent columns and rows, and an arbitrary matrix can be interpolated on the cross entries. Other entries by this cross or pseudo-skeleton approximation are given with errors depending on the closeness of the matrix to a rank-r matrix and as well on the choice of cross. In this paper we extend this construction to d-dimensional arrays (tensors) and suggest a new interpolation formula in which a d-dimensional array is interpolated on the entries of some TT-cross (tensor train-cross). The total number of entries and the complexity of our interpolation algorithm depend on d linearly, so the approach does not suffer from the curse of dimensionality.We also propose a TT-cross method for computation of d-dimensional integrals and apply it to some examples with dimensionality in the range from d=100 up to d=4000 and the relative accuracy of order 10^-10. In all constructions we capitalize on the new tensor decomposition in the form of tensor trains (TT-decomposition).