Complexity of unconstrained L₂-L_p minimization

We consider the unconstrained L_q - L_p minimization: find a minimizer of ∥Ax-b∥^q_q+λ∥x∥ ^p_p for given A ∈ R^m×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 L₂-L_p 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 L_q - L_p problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function ∥̇∥^p_p. In this paper, we show that the L _q - L_p 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.