Volume 63, pp. 247-280, 2025.

RTSMS: Randomized Tucker with single-mode sketching

Behnam Hashemi and Yuji Nakatsukasa

Abstract

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

Full Text (PDF) [1.1 MB], BibTeX , DOI: 10.1553/etna_vol63s247

Key words

tensor decompositions, randomized algorithms, sketching, least-squares, leverage scores, Tikhonov regularization, iterative refinement, HOSVD

AMS subject classifications

68W20, 65F55, 15A69