Nonsmooth, Nonconvex Regularization for Sparse Optimization

Abstract: 

Minimization problems with nonsmooth, nonconvex, perhaps even non-Lipschitz regularization terms have wide applications in image restoration, signal reconstruction and variable selection.  On LpLp non-Lipschitz regularized minimization, we show that finding a global optimal solution is strongly NP-hard. On the other hand, we present lower bounds of nonzero entries in every local optimal solution without  assumptions on the data matrix. Such lower bounds can be used to classify zero and nonzero entries in local optimal solutions and select regularization parameters for desirable sparsity of local optimal solutions. Moreover, we introduce several efficient algorithms including smoothing quadratic regularization algorithms, smoothing trust region Newton methods and interior point algorithms.  Examples with widely used nonsmooth nonconvex regularization terms are presented to illustrate the theory and algorithms.