We consider the unconstrained $L_2$-$L_p$ minimization: find a minimizer of
$\|Ax-b\|^2_2+\lambda \|x\|^p_p$ for given $A \in R^{m\times n}$, $b\in R^m$
and parameters $\lambda>0$, $p\in [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_2$-$L_p$ problem have various attractive features due to the concavity and
non-Lipschitzian property of the regularization function $\|\cdot\|^p_p$. In
this paper, we show that the $L_q$-$L_p$ minimization problem is strongly
NP-hard for any $p\in [0,1)$ and $q\ge 1$, including its smoothed version. On
the other hand, we show that, by choosing parameters $(p,\lambda)$ 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.

本文研究非受限情况下的 $L_2$-$L_p$ 最小化问题，并展示了这个问题的各种吸引人的特性，同时表明 $L_q$-$L_p$ 最小化问题是强 NP 困难问题，但可以通过精心选择参数获得所需的稀疏性，这些结果为凸规则化优化问题的研究和应用提供了新的理论洞察。