Adaptive Randomized Tensor Train Rounding using Khatri-Rao Products

Hussam Al Daas, Grey Ballard, Laura Grigori, Mariana Martinez Aguilar, Arvind K. Saibaba, Bhisham Dev Verma · 2025

Read Adaptive Randomized Tensor Train Rounding using Khatri-Rao Products by Hussam Al Daas, Grey Ballard, Laura Grigori, Mariana Martinez Aguilar, Arvind K. Saibaba, Bhisham Dev Verma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03598.txt.

Introduction

Hussam Al Daas and colleagues design randomized algorithms that squeeze tensors already stored in compressed train format even further. Tensor trains break huge multi-way arrays into chained small pieces, and rounding trims the ranks linking those pieces. Their sketches use Khatri-Rao products, structured random maps that respect the chain form.

When ranks are set ahead, costs match earlier sketch methods. The gain is adaptivity: error can be estimated from the same sketches, with proven guarantees, so ranks can settle at whatever a set tolerance demands. Tests run on synthetic tensors and on parametric kernel problems. Scientific computing leans on such compression to fit otherwise impossible data cubes into memory.

Catalog record

CREATORHussam Al Daas, Grey Ballard, Laura Grigori, Mariana Martinez Aguilar, Arvind K. Saibaba, Bhisham Dev Verma
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-03598

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Adaptive Randomized Tensor Train Rounding using Khatri-Rao Products Thanks: This work was funded in part by the Department of Energy, through awards DE-SC0025262 and DE-SC0025394; the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 810367); the National Science Foundation under grant CCF-1942892; and the Ada Lovelace Centre Programme at the Scientific Computing Department, STFC. Hussam Al Daas, Grey Ballard, Laura Grigori, Mariana Martinez Aguilar, Arvind K. Saibaba, Bhisham Dev Verma 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 uses 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 [ 4 ] . 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 50 × 50\times 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 the adaptivity introduces only a low overhead. keywords Low-rank approximations, Tensor decompositions, Tensor Train, Rounding, Randomized algorithms. MSC 65F55, 65F99, 68W20 1 Introduction A growing range of problems in scientific computing and data analysis involve high-dimensional data represented as tensors—multidimensional generalizations of vectors and matrices. When considering tensors, one must consider the specific tensor format to be used and the associated notions of ranks associated with tensors. Some examples of tensor formats are CP decomposition, Tucker, Tensor Train (TT), Hierarchical Tucker, etc., which have been reviewed in [ 6 , 22 ] . Inspired by the matrix-product-state (MPS), which is widely used in the computational quantum chemistry community [ 35 ] , Oseledets [ 29 ] introduced the TT format to the numerical analysis community. The cost of storing the tensor in the TT-format depends linearly on the number of dimensions. A major challenge is to find a suitable approximation to a tensor in the TT-format with sufficiently small TT-ranks. There are several algorithms to convert a tensor into TT-format, such as TT-SVD [ 29 ] and cross-approximation algorithms [ 13 , 31 , 32 ] . This paper is focused on TT-rounding, which is a special case of TT approximation. Rounding a TT-tensor involves finding a compressed representation of a tensor which is already in TT-format, but perhaps with large ranks. This is an important problem with applications to parametric low-rank kernel approximation [ 21 ] , quantum physics [ 10 ] , high dimensional partial differential equations [ 37 ] , thermal radiation transport [ 15 ] , and the solution of linear tensor equations [ 7 ] . Contributions In this paper, we derive new randomized algorithms for rounding a tensor in the TT-format. The specific contributions of our work are: 1. We propose two new randomized algorithms (Sections 3.2 and 3.3 ) for rounding a TT-tensor. Both algorithms use a random tensor for sketching based on the Khatri-Rao product (KRP). The first algorithm assumes the target ranks are known a priori , whereas the second algorithm takes a prespecified tolerance for the relative error and adaptively determines the ranks. 2. We analyze, in detail, the computational complexity of both algorithms (Sections 3.2 and 3.3 ). While the proposed methods are comparable to existing randomized rounding algorithms, the use of KRPs enables adaptivity, which is missing in existing work. 3. The adaptive randomized algorithm uses a termination criterion based on a randomized Frobenius norm estimator. We also provide an analysis for this estimator (Section 3.4 ). 4. Numerical experiments (Section 4 ) on three different sets of applications—synthetic tensors, parametric kernel low-rank approximation, and numerical solution of a parametric partial differential equation—demonstrate the performance of the method. In these applications, we observe speedups of up to 50\times compared to the deterministic TT-rounding techniques. Additionally, the code required to reproduce our results is available at https://github.com/bhisham123/TT-Rounding-using-KRP-structure.git . Related Work While there have been several developments in structured sketching for various tensor formats [ 8 , 18 , 19 , 26 , 36 ] , we focus our review on TT-rounding. Oseledets proposed a deterministic method for rounding in TT format [ 29 ] . Randomized algorithms for computing the TT decomposition can be found in [ 2 , 11 , 12 , 20 ] with an adaptive implementation in [ 11 ] , but these references focus on tensor compression and not rounding, which is the focus of the present paper. A method for TT-rounding using the Gram matrices was proposed in [ 5 ] . Randomized algorithms for TT-rounding were proposed in [ 4 ] . Of these, the most relevant to this discussion are the Orthogonalize-then-Randomize (Orth-Rand) and Randomize-then-Orthogonalize (Rand-Orth). A more detailed description of these algorithms is given in Sections and . The Rand-Orth approach uses sketching matrices based on the TT-format and is applicable for only the fixed rank case. This approach is much more computationally efficient compared to the Orth-Rand approach, in which the computational cost is dominated by the initial orthogonalization phase. The Orth-Rand approach has an adaptive variant which enables a comparison to our proposed algorithms. Our approach uses sketches using KRPs and enables adaptivity in the TT-rounding. By also using TT-like structured matrices, Kressner et al. [ 24 ] proposed a two-sided, Nyström-like approximation for streaming TT approximation. However, this approach also uses fixed ranks. A comparison of many TT-compression techniques in the context of thermal radiation transport is given in [ 15 ] . A recent paper [ 10 ] also uses randomization with KRP structure to compute single matrix-product-operator times matrix-product-state (MPO-MPS) without considering sums of products or particular structures. Our work is similar to this paper in that our approach also uses sketching matrices with KRP structure and also uses adaptivity. However, our approach can be applied more generally to any TT input and does not specifically exploit the MPO-MPS product structure. We also specialize our approach to exploit the structure of inputs that are sums of TT tensors, as discussed in Section . A detailed comparison between the two approaches is outside the scope of the current paper, and we leave it to future work to develop a version of our algorithm that exploits the specific MPO-MPS structure. The use of KRP sketches for TT-format was also explored in [ 7 ] , but it was not applied to the rounding step. Recent work by [ 9 , 12 , 30 ] has advanced the theoretical understanding of sketching using KRP matrices. 2 Background 2.1 Notation We use boldface Euler script letters to denote tensors (e.g., \bm{{\mathscr{{X}}}} ) and boldface capital letters for matrices (e.g., \bm{{\mathbf{{A}}}} ). For indexing the

Read the complete text