Efficient Sketching-Based Summation of Tucker Tensors

Rudi Smith, Mirjeta Pasha, Andrés Galindo-Olarte, Hussam Al Daas, Grey Ballard, Joseph Nakao, Jing-Mei Qiu, William Taitano · 2026

Read Efficient Sketching-Based Summation of Tucker Tensors by Rudi Smith, Mirjeta Pasha, Andrés Galindo-Olarte, Hussam Al Daas, Grey Ballard, Joseph Nakao, Jing-Mei Qiu, William Taitano (2026) 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-2603-13532.txt.

Introduction

Rudi Smith and co-authors present sketching-based methods for summing tensors in Tucker format. Compressed arithmetic on Tucker tensors must control rank growth and cost as sums are formed. Their approach avoids building large intermediate tensors and works directly on factor matrices and core tensors. Algebraic structure in Khatri-Rao and Kronecker products makes the sketching work. They analyze computational complexity and approximation properties for the method. Tests include synthetic cases, a parameter-dependent elliptic equation via GMRES, and a linear transport problem, with large savings at high accuracy.

Catalog record

CREATORRudi Smith, Mirjeta Pasha, Andrés Galindo-Olarte, Hussam Al Daas, Grey Ballard, Joseph Nakao, Jing-Mei Qiu, William Taitano
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89728
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13532

Browse the full library · About the Tower of Babel

Full text

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

Efficient Sketching-Based Summation of Tucker Tensors Rudi Smith, Mirjeta Pasha, Andrés Galindo-Olarte, Hussam Al Daas, Grey Ballard, Joseph Nakao, Jing-Mei Qiu, William Taitano Abstract We present efficient, sketching-based methods for the summation of tensors in Tucker format. Leveraging the algebraic structure of Khatri-Rao and Kronecker products, our approach enables compressed arithmetic on Tucker tensors while controlling rank growth and computational cost. The proposed sketching framework avoids the explicit formation of large intermediate tensors, instead operating directly on the factor matrices and core tensors to produce accurate low-rank approximations of tensor sums. Furthermore, we analyze the computational complexity and the theoretical approximation properties of the proposed methodology. Numerical experiments demonstrate the effectiveness of our approach on four problems: two synthetic test cases, a parameter-dependent elliptic equation (commonly referred to as the cookie problem ) solved via GMRES, and a one-dimensional linear transport problem discretized via high-order discontinuous Galerkin methods, where repeated tensor summation arises as a core computational bottleneck. Across these examples, the sketching-based summation achieves substantial computational savings while preserving high accuracy relative to direct summation and re-compression. Efficient Sketching-Based Summation of Tucker Tensors \shortdate 2026-03-13 \shortinstitute \msc 15A69, 65F10, 65F55, 65M60, 68W20, 35L65 \novelty This work introduces efficient sketching-based algorithms for the summation of tensors in the Tucker format, by exploiting the algebraic structure of Khatri-Rao and Kronecker products. Unlike existing tensor compression techniques that rely on costly full-format operations or repeated truncations, our approach performs summation directly within the compressed Tucker representation, thereby precluding the explicit formation of large intermediate tensors. The proposed framework combines randomized sketching with structured matrix products to achieve substantial computational savings while empirically maintaining approximation accuracy. We demonstrate the practical efficacy of the method on problems arising from parametric PDEs and high order discontinuous Galerkin discretizations of linear transport problems, where repeated tensor summation is a core computational bottleneck. keywords Tucker, tensor, sketching, Khatri-Rao, Kronecker, parametric PDE, summation 1 Introduction In large-scale scientific computing, tensor computations have become ubiquitous across a wide range of disciplines, including signal processing, computer vision, quantum computing, and the numerical solution of high-dimensional partial differential equations [ 42 , 36 , 8 , 25 , 40 ] . As the dimensionality of the data increases, the storage and computational cost associated with grid-based representations grow exponentially, a phenomenon known as the ‘curse of dimensionality’ [ 7 ] . To address this challenge, low-rank tensor decompositions have emerged as essential tools, including the Canonical Polyadic (CP) [ 11 , 22 ] , Tensor Train (TT) [ 35 ] , and Tucker decomposition [ 43 ] . These formats enable the compression of massive datasets into compact factor representations by exploiting latent multilinear structure. While low-rank formats effectively solve the storage problem for static data, performing arithmetic operations on compressed tensors introduces a new set of computational challenges. A fundamental issue arises during the summation of tensors, an operation that is central to iterative algorithms such as Krylov subspace methods (e.g., GMRES ) for solving linear systems [ 9 ] . Unlike scalar arithmetic, where storage is constant, the rank of a tensor sum is generally the sum of the ranks of its constituents, which consequently means that repeated addition leads to a rapid increase in rank, quickly negating the compression benefits of the decomposition. To maintain computational feasibility in tensorial settings, it is usually standard practice to employ a rounding (truncation) strategy; the tensors are explicitly summed, and the resulting high-rank object is immediately rounded to a target tolerance [ 1 ] . For a Tucker decomposition, the size of the core tensor scales with the product of the ranks along each mode. If we sum d tensors, each with uniform rank r , the formal sum yields a block-sparse core. However, standard truncation procedures require orthogonalizing the factor matrices, which destroys this sparsity and forces the intermediate core tensor to swell to a dense (dr)^{N} array, where N is the order of the tensor. In high-dimensional settings (e.g., N\geq 3 ) or applications involving many summands, this intermediate growth of the core tensor often exceeds available memory, even if the final truncated result is compact. One may decide to truncate more frequently to avoid this memory growth, but this comes at its own cost of performing expensive rounding operations, losing some accuracy, or even rank swelling issues. To address this challenge, we propose a randomized approach to summing Tucker tensors that avoids the explicit formation of high-rank intermediate structures when rounding. Building on core concepts from Randomized Numerical Linear Algebra (RandNLA), our method leverages the concept of sketching where one maps high-dimensional data to a lower-dimensional subspace. Various forms of sketching have already been successfully applied to static tensors [ 37 , 23 , 1 , 33 , 45 ] , which provide a good theoretical underpinning to our summation problem. Notably, [ 28 ] highlights a highly relevant approach for recompressing Hadamard products in the Tucker format. While the Hadamard product affects the core tensor differently than a sum, their central idea of exploiting structure using randomized algorithms with rank-1 (Khatri-Rao) matrices is fundamentally similar to our approach. In this work, we introduce a novel summation algorithm that employs structure preserving sketching operators based on Kronecker and Khatri-Rao products. By applying these sketching operators directly to the factor matrices of the individual summands, we construct a low-dimensional surrogate of the sum’s principal subspace without ever realizing the full, high-rank core tensor. This technique effectively merges the summation and truncation steps into a single procedure, maintaining a bounded rank and memory footprint throughout the computation. To ensure the accuracy of the approximation while avoiding the pitfalls of over-sketching, our approach introduces a novel explicit step to estimate effective ranks prior to sketching. For each mode n , we construct an energy-weighted concatenated factor block \boldsymbol{V}_{n} and compute its corresponding Gram matrix \boldsymbol{B}_{n}=\boldsymbol{V}_{n}^{\mkern-1.5mu\mathsf{T}}\boldsymbol{V}_{n} . The effective rank \widetilde{r}_{n} is then estimated based on the spectral decay of \boldsymbol{B}_{n} , truncating eigenvalues that fall below a relative threshold and adding an oversampling parameter p_{n} to ensure robustness. Upon making this estimation, we employ the subrank heuristic from [ 33 ] specifically for the Kronecker case when reusing factors. While we assume factor reuse throughout this paper, we note that in certain applications—such as those involving highly skewed modes—it may be more appropriate to utilize a separate heuristic without reusing factors, as noted in [ 33 ] . We demonstrate the efficacy and robustness of this approach through a series of numerical experiments. First, we validate the scaling properties of our algorithm on synthetic tensors, showing that our runtime scales favorably with the number of summands compared to deterministic methods, and we justify the frequency of applying the baseline rounding approach. Subsequently, we apply the method to the cookie problem [ 41 ] , a parametric elliptic PDE with geometric inclusions that serves as a good benchmark for high-dimensional solvers [ 1 , 5 , 2 ] . Finally, we demonstrate the practical utility of our method in the context of a high-dimensional linear transport problem solved via the nodal discontinuous Galerkin (NDG) method [ 24 ] , a prototype problem that naturally arises in low-rank kinetic simulations. The remainder of

Read the complete text