High-Performance ⋆ 𝐌 \star_{\bm{{\mathbf{{M}}}}}{} SVD for Big Data Compression

Md Taufique Hussain, Grey Ballard, Aditya Devarakonda, Srinivas Eswar, Naman Pesricha, Vishwas Rao Β· 2026

Read High-Performance ⋆ 𝐌 \star_{\bm{{\mathbf{{M}}}}}{} SVD for Big Data Compression by Md Taufique Hussain, Grey Ballard, Aditya Devarakonda, Srinivas Eswar, Naman Pesricha, Vishwas Rao (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-2605-16058.txt.

Introduction

Hussain and five colleagues build a shared-memory parallel version of the star-M SVD, a tensor tool that shrinks big data with optimality guarantees. Earlier code lived mostly in languages built for ease of use, not speed. Their fast implementation aims to make optimal shrinkage practical for huge scientific data sets. It should also sharpen later analysis.

Catalog record

CREATORMd Taufique Hussain, Grey Ballard, Aditya Devarakonda, Srinivas Eswar, Naman Pesricha, Vishwas Rao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44242
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library Β· About the Tower of Babel

Full text

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

High-Performance ⋆ 𝐌 \star_{\bm{{\mathbf{{M}}}}}{} SVD for Big Data Compression Md Taufique Hussain, Grey Ballard, Aditya Devarakonda, Srinivas Eswar, Naman Pesricha, Vishwas Rao Abstract In the era of big data, effectively compressing large datasets while performing complex mathematical operations is crucial. Tensor-based decomposition methods have shown superior compression capabilities with minimal loss of accuracy compared to traditional matrix methods. Under the ⋆ 𝐌 \star_{\bm{{\mathbf{{M}}}}}{} tensor framework, tensors can be decomposed in a matrix-mimetic way, including using the ⋆ 𝐌 \star_{\bm{{\mathbf{{M}}}}}{} SVD. This tensor SVD has optimality guarantees and has shown exceptional performance on specific types of data, but software implementations have been mostly limited to productivity-oriented languages. In this work, we present our development of a shared-memory parallel, high-performance solution designed to efficiently implement the underlying algorithms. This software will enable optimal compression of extensive scientific datasets, paving the way for enhanced data analysis and insights. Keywords: parallel computing, high-performance computing, tensor decompositions 1 Introduction Truncated tensor-based singular value decompositions based on the star-M ( \star_{\bm{{\mathbf{{M}}}}}{} ) tensor-tensor product mimic the matrix SVD [ 26 ] . An input tensor can be decomposed into the product of three factor tensors with properties of orthogonality and structure that are analogous to the matrix case. Furthermore, this decomposition can be truncated for the purpose of data compression, for example, in a systematic way to determine the optimal representation given either an error tolerance or specified rank parameters. This is possible due to the existence of theoretical guarantees established for the \star_{\bm{{\mathbf{{M}}}}}{} tensor algebra that generalize the Eckart-Young theorem [ 12 ] for low-rank matrix approximation. As described in more detail in Section 2 , given 3-way input tensors, the \star_{\bm{{\mathbf{{M}}}}}{} product is parametrized by an invertible matrix \bm{{\mathbf{{M}}}} and defined by a transformation of the mode-3 fibers of the inputs by \bm{{\mathbf{{M}}}} , independent matrix multiplications of the mode-3 slices, and a back transformation of the output mode-3 fibers by \bm{{\mathbf{{M}}}}^{-1} . The \star_{\bm{{\mathbf{{M}}}}}{} truncated SVD (t-SVD) is thus based on slice-wise matrix SVDs after transformation by the matrix \bm{{\mathbf{{M}}}} , and it is particularly advantageous when the transformation yields many slices to be either low-rank or insignificant relative to other slices. The \star_{\bm{{\mathbf{{M}}}}}{} t-SVD is not agnostic with respect to mode ordering, and the choice of \bm{{\mathbf{{M}}}} can have a substantial effect on the compressibility of a data set. Implementations of \star_{\bm{{\mathbf{{M}}}}}{} algebra and the \star_{\bm{{\mathbf{{M}}}}}{} t-SVD exist in MATLAB and Pythonβ€”see [ 29 , 31 , 24 ] , for exampleβ€”but no high performance implementations have been developed. High performance, parallel software exists for many other tensor formats including CANDECOMP/PARAFAC (CP) [ 17 , 13 , 37 ] , Tucker [ 5 , 22 ] , and Tensor Train [ 2 , 34 ] . The goal of this work is to design an efficient and scalable shared-memory parallel implementation of the fundamental algorithms for computing \star_{\bm{{\mathbf{{M}}}}}{} t-SVD for general multiway data, enabling its use for datasets that were otherwise too large to handle using existing techniques. The core of the \star_{\bm{{\mathbf{{M}}}}}{} t-SVD algorithm is a β€œbatch” of independent matrix SVDs, all of the same dimension, which is ripe for parallelization. In fact, implementations of a batched SVD are emerging in standard libraries like MKL [ 19 , Version 2024.1] and MAGMA [ 11 , Version 2.10.0] . However, the (back-)transformations of the slices necessarily happens in the orthogonal direction, across slices, enabling the decoupling. We show in Section 3 that the transformations can be parallelized via efficient tensor-times-matrix operations that respect the data layout of the tensor in memory and exploits the interface to the batched BLAS [ 1 ] . Two primary algorithms exist for t-SVD: the first specifies a constant rank for the truncation of all slices, and the second specifies an error tolerance that guides the truncation to various ranks across slices. We show how to parallelize the first algorithm using the expert interface to LAPACK, and we explore computation-memory tradeoffs in the design of the second algorithm, which requires analysis of the computed slice-wise singular values to determine ranks. In Section 4 , we consider data sets coming from the domains of climate reanalyses, computational fluid dynamics, and X-ray crystallography. We describe how mode ordering and choice of transformation matrix can affect both performance of the parallel implementations and the quality of the compressed representation. In the case of the climate data, we show the benefits of using tensor-based compression over the standard matrix-based approach used in that field. Our parallel design decisions enable efficient parallel scaling, and we show that on a platform with 64 cores, these datasets can be compressed up to 42\times , 40\times , and 30\times faster than a single core, respectively. Our implementation (which will be made publicly available) enables users to observe speedups of up to 1000\times over existing MATLAB code on a similar machine. Thus, this implementation allows domain scientists to analyze larger data sets in less time, enabling the \star_{\bm{{\mathbf{{M}}}}}{} t-SVD to be applied as broadly as other tensor decomposition techniques. 2 Background This section reviews the mathematical and algorithmic background relevant to our work. We first define notation for tensor and matrix-tensor operations, and define the \star_{\bm{{\mathbf{{M}}}}} -product ( Section 2.1 ). We then introduce the \star_{\bm{{\mathbf{{M}}}}} t-SVD together with its full (t-SVDM-I) and adaptively truncated (t-SVDM-II) variants, whose parallelization and evaluation is the main focus of our work ( Section 2.2 ). Finally, we summarize the Eckart-Young-style optimality results that distinguish the \star_{\bm{{\mathbf{{M}}}}} t-SVD from competing tensor decompositions ( Section 2.3 ) and motivate the need for a shared-memory parallel implementation suited to large scientific datasets ( Section 2.4 ). m r n \hat{\bm{{\mathscr{{U}}}}}\in\mathbb{R}^{m\times r\times n} r p n \hat{\bm{{\mathscr{{G}}}}}\in\mathbb{R}^{r\times p\times n} t-SVDM-I uniform rank r per slice m \rho_{1} \rho_{n} n \hat{\bm{{\mathscr{{U}}}}} (variable rank) \rho_{1} p \rho_{n} n \hat{\bm{{\mathscr{{G}}}}}_{i} (variable rank) t-SVDM-II rank \rho_{i}\leq r varies per slice discarded Figure 1: The output factor structure of t-SVDM-I (left) has uniform ranks across frontal slices which yield coarser error control, whereas t-SVDM-II (right) allows for variable frontal slice ranks \rho_{i} which can adapt to approximation requirements. 2.1 Notation We use uppercase bold letters (e.g., \bm{{\mathbf{{M}}}} ) to denote matrices and calligraphic letters (e.g., \bm{{\mathscr{{A}}}} ) to denote tensors. A three-way tensor \bm{{\mathscr{{A}}}}\in\mathbb{R}^{m\times p\times n} has n frontal slices \bm{{\mathscr{{A}}}}_{:,:,i}\in\mathbb{R}^{m\times p} for i=1,\dots,n . The mode- k unfolding \bm{{\mathbf{{A}}}}_{(k)} arranges the mode- k fibers of \bm{{\mathscr{{A}}}} as columns of a matrix. The mode- k tensor times matrix product (TTM), written \bm{{\mathscr{{A}}}}\mathbin{\times_{\mspace{-2mu}k}}\bm{{\mathbf{{M}}}} for \bm{{\mathbf{{M}}}}\in\mathbb{R}^{J\times n_{k}} , is defined by \bigl(\bm{{\mathscr{{A}}}}\mathbin{\times_{\mspace{-2mu}k}}\bm{{\mathbf{{M}}}}\bigr)_{(k)}\;=\;\bm{{\mathbf{{M}}}}\,\bm{{\mathbf{{A}}}}_{(k)}. The result has the same shape as \bm{{\mathscr{{A}}}} except that mode k has size J instead of n_{k} . \star_{\bm{{\mathbf{{M}}}}} -Product The \star_{\bm{{\mathbf{{M}}}}} -product, introduced by Kilmer et al. [ 26 ] , is a tensor-tensor multiplication parameterized by an invertible matrix \bm{{\mathbf{{M}}}}\in\mathbb{R}^{n\times n} . Given \bm{{\mathscr{{A}}}}\in\mathbb{R}^{m\times p\times n} and \bm{{\mathscr{{B}}}}\in\mathbb{R}^{p\times\ell\times n} , the \star_{\bm{{\mathbf{{M}}}}} -product \bm{{\mathscr{{C}}}}=\bm{{\mathscr{{A}}}}\star_{\bm{{\mathbf{{M}}}}}\bm{{\mathscr{{B}}}}\in\mathbb{R}^{m\times\ell\times n} is defined in three steps. First, both operands are transformed to the \bm{{\mathbf{{M}}}} -domain by applying \bm{{\mathbf{{M}}}} along mode 3, \hat{\bm{{\mathscr{{A}}}}}=\bm{{\mathscr{{A}}}}\mathbin{\times_{\mspace{-2mu}3}}\bm{{\mathbf{{M}}}},\qquad\hat{\bm{{\mathscr{{B}}}}}=\bm{{\mathscr{{B}}}}\mathbin{\times_{\mspace{-2mu}3}}\bm{{\mathbf{{M}}}}. Second, the n pairs of frontal slices are multiplied independently in the transform domain, \hat{\bm{{\mathscr{{C}}}}}_{:,:,i}\;=\;\hat{\bm{{\mathscr{{A}}}}}_{:,:,i}\,\hat{\bm{{\mathscr{{B}}}}}_{:,:,i},\qquad i=1,\dots,n, where each product is an ordinary matrix multiplication. Third, the result is mapped back to the original domain by applying \bm{{\mathbf{{M}}}}^{-1} along mode

Read the complete text