Abstract
The low-tubal-rank tensors have been recently proposed to model real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of elements selected uniform at random. We propose a fast iterative algorithm, called Tubal-Alt-Min, that is inspired by similar approach for low rank matrix completion. The unknown low-tubal-rank tensor is parameterized as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-Alt-Min alternates between estimating those two tensors using tensor least squares minimization. We note that the tensor least squares minimization is different from its counterpart and nontrivial, and this paper gives a routine to carry out this operation. Further, on both synthetic data and real-world video data, evaluation results show that compared with the tensor nuclear norm minimization, the proposed algorithm improves the recovery error by orders of magnitude with smaller running time for higher sampling rates.