Adaptive Randomized Tensor Train Rounding Using Khatri–Rao Products

Abstract. Approximating a tensor in the tensor train (TT) format has many important applications in scientific computing. Rounding a TT tensor involves further compressing a tensor that is already in the TT format. This paper proposes new randomized algorithms for TT-rounding that use sketches based on Khatri-Rao products (KRP). When the TT-ranks are known in advance, the proposed methods are comparable in cost to the sketches that used a sketching matrix in the TT-format [Al Daas et al., SIAM J. Sci. Comput., 45 (2023), pp. A74–A95]. However, the use of KRP sketches enables adaptive algorithms to round the tensor in the TT-format within a fixed user-specified tolerance. An important component of the adaptivity is the estimation of error using KRP sketching, for which we develop theoretical guarantees. We report numerical experiments on synthetic tensors, parametric low-rank kernel approximations, and the solution of parametric partial differential equations. The numerical experiments show that we obtain speed-ups of up to [Formula: see text] compared to deterministic TT-rounding. Both the computational cost analysis and numerical experiments verify that the adaptive algorithms are competitive with the fixed-rank algorithms, suggesting that adaptivity has a small overhead. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/bhisham123/TT-Rounding-using-KRP-structure.git and in the supplementary materials ( M181708_Supplementary_Materials_1.pdf [459KB], TT-Rounding-using-KRP-structure-main.zip [12.8MB]). [Formula: see text]