On The Relaxation of Orthogonal Tensor Rank and Its Nonconvex Riemannian Optimization for Tensor Completion

Natural extension of matrix rank has attracted interest toward a parsimonious representation and completion of a tensor with partial observation. In this paper, we focus on orthogonal tensor rank and discuss its nonconvex relaxation and minimization. Accordingly, we present a completion algorithm using the proximal alternating direction method of multipliers for three-way tensors, wherein we solve a minimization problem on the orthogonal group using the Riemannian subgradient descent. We also analyze the global convergence of the proposed algorithm. In a simulation experiment, we show that our algorithm could extract the parsimonious structure of a tensor with partial observation. We also demonstrate, against both synthetic and realistic data, a superior completion performance of our proposed algorithm to some recent methods.