Low Rank Recovery Based On L₀ Norm Non-convex Surrogate Methods And Its Application

In resent years,low rank recovery problems are getting more attention,and widely used for dimension reduction and data analysis.Low rank recovery is proposed to exploit low-dimensional structure in high-dimensional data.Because the original low rank recovery preoblems are involve with rank function and L0 norm.This causes that the most of models are NP-hard.A common solution is to use the corresponding convexly relaxed problems to approximate the original problems for effective solving.For most single subspace low rank models,its exact recovery has been proved theoretically:if some conditions are satisfied,the convex optimization methods can exactly recover the real solution of the problems.However,since these strictly conditions are hardly met in reality,which means that the solution by convex problem can be far away from the true value.Therefore,to balance the validity and solvability of the model,general solver for two types of low rank recovery frames are studied.And low rank recovery method based on non-convex surrogate and its related applications in outlier pursuit and image denoising problems are discussed in this work.The main contributes of this paper are list in the following:(1)A new fixed-point algorithm(GAI)is given for solving a key optimization problem to global optimality with superlinear convergence rate.Based on generalized proximal gradient and GAI,a general solverfor first kind of low rank recovery frame is given in this paper.It is proven in theoretically and experimentally that the proposed algorithm is more efficient compared with traditional method.(2)For second kind of low rank recovery frame,this paper presents a variant algorithm of block coordinate descent algorithm.Based on that,the original frame is splited into two non-convex subproblems.Besides,an important theorem is given to solve the non-convex subproblems.Therefore,the general solver for the second kind of low rank recovery frame is obtained.The validity of the proposed solver is proved theoretically and experimentally.In addition,it can be seen from the experiment that low rank recovery methods based on non-convex surrogate achieve a better results compared with the convex method in the outlier persuit problems.(3)This paper gives a novel non-convex surrogate method using parameterize method(include parameterized norm and parameterized nuclear norm),and a new non-convex model is obtained based on the two norms.Experiments illustrate the effectiveness of the proposed approach in the image denoising problems.