A Sequentially Truncated Higher Order Singular Value Decomposition-Based Algorithm for Tensor Completion

The problem of recovering missing data of an incomplete tensor has drawn more and more attentions in the fields of pattern recognition, machine learning, data mining, computer vision, and signal processing. Researches on this problem usually share a common assumption that the original tensor is of low-rank. One of the important ways to capture the low-rank structure of the incomplete tensor is based on tensor factorization. For the traditional tensor factorization algorithms, the tensor ranks should be specified ahead, which is not reasonable in real applications. To overcome this drawback, an adaptive algorithm is first presented based on sequentially truncated higher order singular value decomposition (ST-HOSVD) for fast low-rank approximation of complete tensor, in which the tensor ranks can be obtained adaptively. Then for tensor with missing data, we use adaptive ST-HOSVD and the average operator of low-rank approximation to improve the accuracy of the fulfilled tensor. Convergence analysis of the proposed algorithm is also given in this paper. The experimental results on 14 image datasets and three video datasets show that the proposed method outperforms the state-of-the-art methods in terms of running time and the accuracy.