A Fast Algorithm for Weighted Tensor Rank Minimization

Recently, tensor rank minimization problem with the sum of nuclear norm(SNN) and its variants has received significant attention. Convex relaxations of tensor rank guarantee the global convergence. However, the sum of nuclear norm(SNN) is not a tight relaxation and the computation of full SVD is very expensive. In this paper, we extend the weighted matrix rank to tensor rank to balance the penalization of different singular values. We also use a randomized projection technique to accelerate the computation. The experiments confirm the benefits of our choice of regularization and the proposed algorithms outperform state-of-the-art algorithms on synthetic and real datasets.