Efficient sparse low-rank tensor completion using the Frank-Wolfe algorithm

Abstract

Tensor data are used widely in real-world applications, especially in completing the missing entries in partially observed multilinear data. However, most tensor problems are NP-hard, and low-rank tensor completion is much more difficult than low-rank matrix completion. In this paper, we propose a time and space-efficient low-rank tensor completion algorithm by using the scaled latent nuclear norm for regularization and the Frank-Wolfe (FW) algorithm for optimization. We show that all the steps can be performed efficiently. In particular, Frank-Wolfe's linear subproblem has a closed-form solution which can be obtained by rank-one SVD. By using power method, it only includes matrix and vector multiplications to obtain rank-one SVD, which are efficient especially when the tensor is sparse. It is also very efficient to search for the best step size, where there is a simple closed-form solution. Moreover, by utilizing sparsity of the observed tensor, we only need to maintain sparse tensor entries and a set of small basis matrices to further reduce the time and space requirements. To alleviate the memory problem caused by maintaining all the bases, we also propose a basis reduction process to reduce the number of bases. Experimental results show that the proposed algorithm is more accurate, much faster and more scalable than the state-of-the-art.

Date of Award	2017
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology