Parallel Randomized Tucker Decomposition Algorithms

DOI10.1137/22M1540363MaRDI QIDQ6418273zbMATH OpenFDO

Authors Rachel Minster, Zitong Li, Grey Ballard

Publication date 23 November 2022

Full work available at URL https://doi.org/10.1137/22M1540363

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: The Tucker tensor decomposition is a natural extension of the singular value decomposition (SVD) to multiway data. We propose to accelerate Tucker tensor decomposition algorithms by using randomization and parallelization. We present two algorithms that scale to large data and many processors, significantly reduce both computation and communication cost compared to previous deterministic and randomized approaches, and obtain nearly the same approximation errors. The key idea in our algorithms is to perform randomized sketches with Kronecker-structured random matrices, which reduces computation compared to unstructured matrices and can be implemented using a fundamental tensor computational kernel. We provide probabilistic error analysis of our algorithms and implement a new parallel algorithm for the structured randomized sketch. Our experimental results demonstrate that our combination of randomization and parallelization achieves accurate Tucker decompositions much faster than alternative approaches. We observe up to a 16X speedup over the fastest deterministic parallel implementation on 3D simulation data.

Recommendations

• A randomized tensor singular value decomposition based on the t-product.
• Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format
• Parallel Algorithms for Computing the Tensor-Train Decomposition
• A Practical Randomized CP Tensor Decomposition

Cited in

(8)

• Software for Sparse Tensor Decomposition on Emerging Computing Architectures
• Parallel approximation of multidimensional tensors using GPUs
• Randomized tensor wheel decomposition
• A direct method for computing the complex-valued triple decomposition of third-order tensors
• Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
• Randomized low-rank approximations beyond Gaussian random matrices
• Intrinsic Low-Tucker-Rank Theory and Unified Tensor CUR Decomposition for High-Dimensional Hyperinterpolation
• Randomized Tucker-Sketched GMRES

This page was built for publication: Parallel Randomized Tucker Decomposition Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6418273)