Tucker factorization with missing data with application to low-$n$-rank tensor completion

Abstract

The problem of tensor completion arises often in signal processing and machine learning. It consists of recovering a tensor from a subset of its entries. The usual structural assumption on a tensor that makes the problem well posed is that the tensor has low rank in every mode. Several tensor completion methods based on minimization of nuclear norm, which is the closest convex approximation of rank, have been proposed recently, with applications mostly in image inpainting problems. It is often stated in these papers that methods based on Tucker factorization perform poorly when the true ranks are unknown. In this paper, we propose a simple algorithm for Tucker factorization of a tensor with missing data and its application to low-$n$-rank tensor completion. The algorithm is similar to previously proposed method for PARAFAC decomposition with missing data. We demonstrate in several numerical experiments that the proposed algorithm performs well even when the ranks are significantly overestimated. Approximate reconstruction can be obtained when the ranks are underestimated. The algorithm outperforms nuclear norm minimization methods when the fraction of known elements of a tensor is low.