Nonconvex Relaxation Methods For Sparse Recovery Problem

Recently, the sparse recovery problems including compressed sensing, low rank matrix recovery and low rank tensor recovery have attracted a lot of attentions since it has wide applications in many practical areas. Fruitful results have been gained based on the research of the convex relaxation model; while the nonconvex relaxation model has more advantages than the convex relaxation model, but the model with respect to the nonconvex relaxation is harder to solve compared to the convex relaxation model. Research based on the algorithms has become one of the major focuses in this field. In this paper, we design e?ective algorithms for the non-convex relaxation models of these three sparse recovery problems, and prove the convergence results. Preliminary numerical results show the e?ectiveness of the proposed algorithms. Specifically, the paper reads as follows:First, we discuss the properties of the entropy function, establish a smoothing approximation model for the nonconvex lpquasi-norm minimization problem, propose a general framework of smoothing algorithm for the smoothing model, and give the convergence analysis of the algorithm by proving that any accumulation point of the sequence generated by the smoothing algorithm is a stationary point of the lpminimization problem.Moreover, we give the lower bound estimation of the nonzero entries for the stationary point of the smoothing problem, which provides further guarantee for obtaining the sparse solution from the algorithm. Numerical experiments show that the proposed model and algorithm are e?ective for solving the sparse signal recovery problem.Second, we establish a smoothing approximation model for the unconstrained L2-Mpminimization problem, give the subdi?erential formula of the nonconvex regular term in the model and the proximal operator of the weighted nuclear norm, and then design a reweighted nuclear norm minimization algorithm for solving the unconstrained L2-Mp minimization problem. Also, we prove that any accumulation point of the sequence generated by the algorithm is a stationary point of the original problem, which ensures the convergence of the algorithm. Numerical experiments on random created matrix completion and image recovery problems indicate that the proposed algorithm has better recoverability compared to existing related algorithms.Last, we establish a nonconvex Lprelaxation model for the low Tucker rank tensor recovery problem, and equivalently transform it to a nonconvex minimization problem with separable structure by introducing a series of auxiliary variables, then propose the accurate and non-accurate non-convex alternating direction method of multipliers to solve it. Also, we give the convergence results of the proposed algorithms under certain conditions. Numerical experiments based on simulated data and true data show the e?ectiveness of the proposed algorithm for solving the low Tucker rank tensor recovery problem.