Study on A New Nonconvex Surrogate of Zero-Norm Function and Its Application

Based on the SCAD (Smoothly Clipped Absolute Deviation) function and the elastic net function, a new zero-norm nonconvex surrogate function(EN-SCAD function) is proposed, which is the difference between the elastic net function and a continuous differentiable convex function, thus is a DC (difference of convex) function. Then, the EN-SCAD function is applied to the sparse linear regression problem, and the EN-SCAD nonconvex surrogate model is established, and the statistical error bound between the stationary point of the model and the true sparse vector is obtained under appropriate restricted strong convex condition. Secondly, a multi-stage convex relaxation algorithm is designed according to the EN-SCAD nonconvex surrogate model, and obtain the statistical error bounds between the columns of iterative points generated by the algorithm and the true sparse vector. Finally, comparing the numerical effects of the algorithm designed based on the EN-SCAD nonconvex surrogate model with a convex relaxation method for adaptive elastic net. Numerical experimental results show that when the column vectors of the sampling matrix are strongly correlated, the estimation error produced by the algorithm based on the EN-SCAD nonconvex surrogate model is smaller than that produced by the convex relaxation method for adaptive elastic net.