RTSMS: Randomized Tucker with single-mode sketching

2023/11/24 by Hashemi, Behnam, Nakatsukasa, Yuji · 2 citations
#15A69 #65F55 #68W20 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2311.14873

Abstract

We propose RTSMS (Randomized Tucker via Single-Mode-Sketching), a randomized algorithm for approximately computing a low-rank Tucker decomposition of a given tensor. It uses sketching and least-squares to compute the Tucker decomposition in a sequentially truncated manner. The algorithm only sketches one mode at a time, so the sketch matrices are significantly smaller than alternative approaches. The algorithm is demonstrated to be competitive with existing methods, sometimes outperforming them by a large margin.

Cited by

• Adaptive Randomized Tensor Train Rounding using Khatri-Rao Products
• Hierarchical Tucker Low-Rank Matrices: Construction and Matrix-Vector Multiplication

Related

• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
• Practical Sketching Algorithms for Low-Rank Tucker Approximation of Large Tensors
• Parallel Randomized Tucker Decomposition Algorithms
• Efficient algorithms for Tucker decomposition via approximate matrix multiplication
• Efficient randomized algorithms for the fixed Tucker-rank problem of Tucker decomposition with adaptive shifts