TT-cross approximation for multidimensional arrays

Abstract: As is well known, a rank- matrix can be recovered from a cross of 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- matrix and as well on the choice of cross. In this paper we extend this construction to -dimensional arrays (tensors) and suggest a new interpolation formula in which a -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 linearly, so the approach does not suffer from the curse of dimensionality. We also propose a TT-cross method for computation of -dimensional integrals and apply it to some examples with dimensionality in the range from up to and the relative accuracy of order . In all constructions we capitalize on the new tensor decomposition in the form of tensor trains (TT-decomposition). [Copyright &y& Elsevier]