Low rank and sparse decomposition based on extended LLp norm

The problem of decomposing a given matrix into its low-rank and sparse components, known as robust principle component analysis (RPCA), has found many applications in variety of fields. In this problem, the goal is to recover the two components through constrained minimization of a combination of the rank function and l(0) norm. Oftentimes, exact recovery of the low-rank component is desired. Since the problem is NP-Hard, a convex relaxation where nuclear norm and l(1) norm are utilized to induce low-rank and sparsity is used. However, it may obtain suboptimal results since the nuclear norm cannot well approximate the rank function. This paper addresses the low-rank and sparse decomposition (LRSD) problem by utilizing a new nonconvex approximation function for the rank. In our LRSD approach, the nonconvex LLp norm is extended on singular values to obtain a new surrogate, called eLL(p), for the rank function. To solve the associated minimization problem, an efficient algorithm based on alternating direction multiplier method (ADMM) and Majorization-Minimization (MM) algorithm is developed. To verify the effectiveness of the proposed method, it is applied to the synthetic data and real applications including face image shadow removal and image denoising. Experimental results show the effectiveness of the proposed method compared with the other methods in terms of the recovery errors and objective evaluations. In real applications of the images, our proposed method achieves higher recovery accuracy in a less time.