Tensor Recovery via Nonconvex Low-Rank Approximation

The low-rank tensor recovery is a powerful approach to depict the intrinsic structure within high-dimensional data, and has been extensively leveraged in many real-world applications. Conventional techniques of low-rank recovery formulate it as a rank minimization problem, then approximate the rank function with the convex relaxation. In this paper, we propose a new tensor logarithmic norm as the nonconvex rank surrogate. Compared with the convex surrogate of nuclear norm, the proposed logarithmic norm is proved to be a tighter approximation to the tensor average rank, and thus is more sparsity-encouraging to extract the underlying low-rank information. Although minimizing the logarithmic norm leads to a nonconvex optimization problem, we rigorously derive its closed-form solution with the guarantee of local optimality. Experimental results demonstrate the strong convergence behavior of the proposed algorithm. In the real-world application of video recovery, our method outperforms several state-of-the-art methods and shows the remarkable recovery accuracy.