A PRACTICAL MODE-PARALLEL IMPLEMENTATION OF THE (H-)TUCKER DECOMPOSITION VIA RANDOMIZATION

Martina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni · 2026

Read A PRACTICAL MODE-PARALLEL IMPLEMENTATION OF THE (H-)TUCKER DECOMPOSITION VIA RANDOMIZATION by Martina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni (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-21379.txt.

Introduction

Iannacito and co-authors give a mode-parallel implementation of the Tucker and H-Tucker tensor decompositions using randomization. Low rank tensor factorizations reveal hidden structure in multidimensional data, but they cost heavy energy and memory. Most methods parallelize within each mode while still visiting modes one by one. Their strategies work along all modes at once, using fiber sampling and randomized range finding. Tests show lower run time and storage, with good scaling on HPC systems.

Catalog record

CREATORMartina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95503
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

A PRACTICAL MODE-PARALLEL IMPLEMENTATION OF THE (H-)TUCKER DECOMPOSITION VIA RANDOMIZATION Martina Iannacito, Sascha Portaro, Davide Palitta, Claudio Arlandini, Domitilla Brandoni Abstract In the last decades, tensors have emerged as the right tool to represent multidimensional data in a compact yet informative manner. Moreover, it is well-known that by performing low-rank factorizations of such tensors one is often able to effectively unveil possible hidden structure in data, mainly due to unexpected dependencies among the different variables encoded in the given tensor. However, computing these factorizations is extremely energy-consuming and memory-demanding, especially for high-dimensional tensors, namely those with a large number of modes. In this paper we focus on two state-of-the-art tensor decompositions: the Tucker and H-Tucker decompositions. We propose novel numerical strategies able to perform these factorizations in a mode-parallel fashion, that is the operations required by the algorithm along all modes are performed in parallel. This is in contrast to what is achieved by many procedures available in the literature that parallelize some of the operations along each mode, e.g., tensor-times-matrix steps, while still visiting one mode at the time in a sequential manner. Our strategies make use of cutting-edge randomization techniques comprising fiber sampling and randomized range-finding steps. We provide upper bounds on the expected value of the error provided by our factorizations while a panel of numerical results showcases the potential of our approach in reducing both the running time and the storage demand of the whole procedure. Moreover, experiments carried out in HPC environments illustrate the good scaling of our mode-parallel approach. 1 Introduction In the last years, tensors have become one of the most suitable mathematical objects for representing large datasets and their fundamental role is widely recognized. Tensor techniques find application in a variety of different fields including deep neural networks [ 22 ] , image classification and recognition [ 24 , 32 ] , computer vision [ 9 ] , recommender systems [ 23 , 18 ] , signal processing [ 25 ] , and many others. The main feature of tensor techniques is the possibility of encoding data of very different nature in a single, compact tool that, on one hand, obeys to a strict mathematical formalism and, on the other hand, has the flexibility of being represented by means of one’s favorite tensor format. A non complete list of tensor formats available in the literature include the Tucker format [ 29 ] and its hierarchical counterpart, the H-Tucker format [ 12 , 11 ] , Tensor-Train (TT) [ 20 ] , and the Canonical Polyadic (CP) format [ 14 ] , to name a few. Further details on these widely used tensor formats can be found in [ 3 ] . Each format comes with its own arithmetic and related pros and cons in terms of computational complexity and interpretability features. In this paper we focus on the Tucker and H-Tucker formats as these are among the most widely used tensor formats for compressing and revealing hidden patterns in data while preserving its multiway nature. Given an order- d tensor \mathbfcal{X}\in\mathbb{R}^{n_{1}\times\cdots\times n_{d}} , representing it in the Tucker format means factorizing \mathbfcal{X} as the product of d factor matrices {\mathbf{{U}}}_{i}\in\mathbb{R}^{n_{i}\times r_{i}} and an order- d tensor of smaller size \mathbfcal{S}\in\mathbb{R}^{r_{1}\times\cdots\times r_{d}} , r_{i}\leq n_{i} for all i=1,\ldots,d , such that \mathbfcal{X}=\mathbfcal{S}\times_{1}{\mathbf{{U}}}_{1}\times_{2}\cdots\times_{d}{\mathbf{{U}}}_{d}, (1) where \times_{i} denotes the mode- i product; see section 2.2 . Each factor matrix {\mathbf{{U}}}_{i} tries to capture most of the information of the column space of the corresponding tensor matricization, whose column number grows exponentially with d . Classical Tucker decomposition algorithms form the d tensor matricizations and factorize them by SVD; this approach is known as the High-Order SVD (HOSVD) [ 8 ] . One of the main disadvantages of the Tucker format ( 1 ) is the allocation of the core tensor \mathbfcal{S}\in\mathbb{R}^{r_{1}\times\cdots\times r_{d}} whose number of entries grows exponentially with the number of modes d . To reduce this important storage cost, Hackbusch proposed the H-Tucker format [ 12 ] which is able to attain memory requirements that now scale linearly with d . This is achieved by relying on a binary tree structure to factorize a given tensor, forming and decomposing a tensor matricization for each tree node; see [ 11 ] and also section 4 for further details. The computation of both the Tucker and H-Tucker decompositions requires performing a significant number of SVDs of large dimensional objects oftentimes leading to excessive computational costs and memory requirements. The drawbacks of these deterministic algorithms have motivated the search for more efficient methods and randomization-based approaches are frequently employed to decrease these computational costs, boosting algorithmic performance; see, e.g., [ 1 ] . Many of these techniques simply amount to applying state-of-the-art randomized techniques for matrix (low-rank) approximation to each matricization of the tensor of interest. While this approach often reduces the running time of the overall procedure, it does not cut down its storage demand due to the requirement of assembling the full matricizations. In this paper we present a new Tucker decomposition technique combining tensor fiber sampling and randomized range-finding techniques. In particular, thanks to the fiber sampling step we overcome the computational costs and memory requirements of forming any tensor matricizations, while the range-finding step improves the approximation of the tensor matricization column space. Avoiding the allocation of any matricization is key to attain a practical mode-parallel algorithm for Tucker decomposition. Indeed, while the original algorithm is embarrassingly parallelizable mode-wise, the need of assembling tensor matricizations, whose number of entries is equal to the one of the original tensor, makes it impractical. Now, thanks to our fiber sampling step, we are able to allocate only a sizable number of fibers on each computational node thus attaining an actual mode-parallel approach able to reduce inter-node communication costs and local memory requirements. Other contributions available in the literature proposed a parallel implementation of the Tucker decomposition; see, e.g., [ 2 , 6 , 16 ] . However, their main focus is to increase the efficiency of Tensor-Times-Matrix (TTM) operations via parallelization. Our goal here is different. Our mode-wise approach fully unlocks the natural parallel nature of the Tucker decomposition by overcoming the need of allocating d copies of the entire original tensor. Clearly, along each mode, parallel TTMs can be then performed by taking inspiration from the aforementioned works to further improve the performance and scalability of the overall method. For the H-Tucker decomposition, instead, we have not been successful at finding any work considering the parallelization of this algorithm. Starting from our randomized Tucker decomposition, we introduce the same modifications in the H-Tucker decomposition. Since, in this case, the number of nodes in the decomposition tree is usually larger than d , the computational benefits of our randomized H-Tucker variant are even more appreciable. Here is a synopsis of the paper. In section 2 we report some preliminaries background material like the notation we adopt throughout the paper (section 2.1 ), some basic concepts and definitions for handling tensors (section 2.2 ), and the randomized SVD (RSVD) approach for matrices (section 2.3 ) presented in [ 13 ] . Section 3 starts with briefly recalling the Tucker decomposition, its approximation by HOSVD, and the

Read the complete text