Complexity of Unconstrained L₂-Lₚ Minimization

الأصل · EN

We consider the unconstrained L₂-Lₚ minimization: find a minimizer of Ax-b²₂+λxᵖₚ for given A ∈ Rᵐ× ⁿ, b∈ Rᵐ and parameters λ>0, p∈ [0,1). This problem has been studied extensively in variable selection and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the L₂-Lₚ problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function ·ᵖₚ. In this paper, we show that the Lq-Lₚ 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.