Randomized Algorithms for Low-Rank Tensor Completion in TT-Format

Abstract

Tensor completion is a crucial technique for filling in missing values in multi-dimensional data. It relies on the assumption that such datasets have intrinsic low-rank properties, leveraging this to reconstitute the dataset using low-rank decomposition or other strategies. Traditional approaches often lack computational efficiency,particularly with singular value decomposition (SVD) for large-scale tensor. Furthermore, fixed-rank SVD methods struggle with determining a suitable initial rank when data are incomplete. This paper introduces two novel randomized algorithms designed for low-rank tensor completion in tensor train (TT) format, named TTrandPI and FPTT. The TTrandPI algorithm integrates randomized tensor train (TT) decomposition with power iteration techniques, thereby enhancing computational efficiency and accuracy by improving spectral decay and minimizing tail energy build-up. Meanwhile, the FPTT algorithm utilizes a fixed-precision low-rank approximation approach that adaptively selects tensor ranks based on error tolerance levels, thus reducing the dependence on a predetermined rank. By conducting numerical experiments on synthetic data, color images, and video sequences, both algorithms exhibit superior performance compared to some existing methods.