Black box cross approximation for multidimensional arrays

In our new paper, “TT cross approximation for multidimensional arrays” a new formula is presented for the recovery of a high-dimensional array from a part of its entries, provided that the array possesses some low-rank structure, namely it has small compression ranks (for example, a tensor of low canonical rank satisfies this). The only previous work known to us is the work by Grasedyck, Espig and Hackbusch, which uses interpolation on “fiber crosses”. It is based on canonical decomposition, requires minimization methods and there is no guarantee that the method will work even in the exact. Our new representation solves this problem completely, and it is shown, in particular, that if the rank of the tensor is r, then it can be exactly recovered from O(dnr^2) of its entries. This is a natural generalization of the skeleton decomposition of matrices and it becomes possible due to the replacement of the canonical format by the TT format, which is related to a series of matrix decompositions.   It is also proven that the TT approximation obtained by a sequence of SVD decompositions can be worser only up to a factor of \sqrt(d-1)  then the optimal TT approximation in the Frobenious norm.

The simple alternating maxvol algorithm is presented for the computation of the TT-cross decomposition of a black box tensors, which has complexity linear in the dimensions, and its effectiveness is illustratred on several examples in  multidimensional integrations, with dimensions of order hundreds and even thousands. The algorithm is implemented as part of TT Toolbox and the code will be presented shortly after.