Complexity of unconstrained L₂-L_p minimization

We consider the unconstrained Lq - Lp minimization: find a minimizer of ∥Ax-b∥qq+λ∥x∥ pp for given A ∈ Rm×n and parameters λ >0, p ∈[0, 1) and q≥ 1. This problem has been studied extensively in many areas. Especially, for the case when q=2, this problem is known as the L2-Lp minimization problem and has found its applications in variable selection problems and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the Lq - Lp problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function ∥̇∥pp. In this paper, we show that the L q - Lp minimization problem is strongly NP-hard for any p ∈ [0,1) and q≥ 1, including its smoothed version. On the other hand, we show that, by choosing parameters (p,λ) carefully, a minimizer, global or local, will have certain desired sparsity. We believe that these results provide new theoretical insights to the studies and applications of the concave regularized optimization problems.