Logarithmic Norm Regularized Low-Rank Factorization for Matrix and Tensor Completion

Matrix and tensor completion aim to recover the incomplete two- and higher-dimensional observations using the low-rank property. Conventional techniques usually minimize the convex surrogate of rank (such as the nuclear norm), which, however, leads to the suboptimal solution for the low-rank recovery. In this paper, we propose a new definition of matrix/tensor logarithmic norm to induce a sparsity-driven surrogate for rank. More importantly, the factor matrix/tensor norm surrogate theorems are derived, which are capable of factoring the norm of large-scale matrix/tensor into those of small-scale matrices/tensors equivalently. Based upon surrogate theorems, we propose two new algorithms called Logarithmic norm Regularized Matrix Factorization (LRMF) and Logarithmic norm Regularized Tensor Factorization (LRTF). These two algorithms incorporate the logarithmic norm regularization with the matrix/tensor factorization and hence achieve more accurate low-rank approximation and high computational efficiency. The resulting optimization problems are solved using the framework of alternating minimization with the proof of convergence. Simulation results on both synthetic and real-world data demonstrate the superior performance of the proposed LRMF and LRTF algorithms over the state-of-the-art algorithms in terms of accuracy and efficiency.