TT-cross approximation for multidimensional arrays (Q126160): Difference between revisions

It is well known that 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 the cross. In the present paper the authors are extending 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 the proposed interpolation algorithm depend on \(d\)-linearly, so the approach does not suffer from the curse of dimensionality. The main contribution of the paper is the new interpolation formula in \(d\) dimensions. It generalizes the skeleton (dyadic) decomposition to \(d\) dimensions via the TT format, and it turns out that if all compression ranks are bounded then it is sufficient to compute only part of the elements of a tensor in certain prescribed positions and use them to completely recover this tensor. Thus, from a virtual (black-box) tensor on input it become possible to get a tensor-train representation of this tensor on output. A simple variant of the TT cross algorithm is presented and convincing numerical experiments are given. Then the TT cross algorithm is applied to approximate some black-box tensors arising in the numerical computation of \(d\)-dimensional integrals. Throughout the paper several notations from linear algebra are used that are now becoming standard. For the purpose of not distracting the reader with notations, the authors are not giving them in detail, and are referring to previous works. Standard MATLAB notations are also used for handling tensor and matrix operations, especially to describe algorithms. It is important to note that the TT-cross formula represents a tensor exactly if its auxiliary unfolding matrices are of low rank. The latter is always the case when a tensor has a low canonical rank. In other cases this formula can represent a tensor approximately. For general TT approximations, in this regard it is proved that with the best possible accuracies for approximations of predetermined ranks to the unfolding matrices, there exists a TT approxima-tion with error bounded from above. It immediately follows that if there is the best possible accuracy for TT approximations with fixed compression rank bounds, then the constructions provide a quasi-optimal TT approximation with the error bounded from above. A simple variant of the TT-cross approximation method is proposed in the case when a tensor is given as a black box by a procedure for computation of any required element. This method allows obtaining TT approximations to some functional tensors in really many dimensions in a moderate time (up to a few minutes) on a notebook. Then, as soon as the tensors are available in the TT format, it becomes possible to perform many basic operations with these tensors in a very efficient way. A TT-cross method for computation of \(d\)-dimensional integrals is also proposed. It is applied to some examples with dimensionality in the range from \(d = 100\) up to \(d = 4000\) and the relative accuracy of order \(-10\). All in all, the presented interpolation method for high-dimensional tensors is given with a complete proof in the exact case, and numerical experiments confirm that it is a very efficient approximation tool for black-box tensors.