Randomized Algorithms for Multilinear UTV Decomposition

ABSTRACT Truncated multilinear UTV decomposition (TMLUTVD) is an efficient method to extract the most dominant features of a given tensor in various practical applications, such as tensor tracking. However, the computation of TMLUTVD can be time‐consuming, especially for large‐scale data. Randomized methods are known for their ability to reduce computational costs, particularly when dealing with the low‐rank approximation of large tensors. Therefore, in this paper, we develop randomized algorithms for computing the multilinear UTV decomposition. Specifically, we propose randomized versions of TMLUTVD using randomized sampling schemes and the power method technique, which is an extension of the existing randomized matrix method. They are more efficient when applied to very large datasets compared with deterministic methods, and a detailed probabilistic error analysis of these algorithms is provided. We further introduce two novel variants of these randomized algorithms, based on distinct computational challenges inherent in processing large‐scale datasets. The first variant can adaptively find a low‐rank representation that satisfies a given tolerance when the target rank is not known in advance. The second variant preserves the original tensor structure and is particularly effective for managing large‐scale sparse tensors that are challenging to load into memory. Some numerical results are presented to illustrate the efficiency and effectiveness of the proposed methods.