The Rank-1 Completion Problem for Cubic Tensors

This paper studies the rank-1 tensor completion problem for cubic tensors. First of all, we show that this problem is equivalent to a special rank-1 matrix recovery problem. When the tensor is strongly rank-1 completable, we show that the problem is equivalent to a rank-1 matrix completion problem and it can be solved by an iterative formula. For other cases, we propose both nuclear norm relaxation and moment relaxation methods for solving the resulting rank-1 matrix recovery problem. The nuclear norm relaxation sometimes returns a rank-1 tensor completion, while sometimes it does not. When it fails, we apply the moment hierarchy of semidefinite programming relaxations to solve the rank-1 matrix recovery problem. The moment hierarchy can always get a rank-1 tensor completion, or detect its nonexistence. Numerical experiments are shown to demonstrate the efficiency of these proposed methods.