Complexity of Unconstrained L_2-L_p Minimization

Details Complexity of Unconstrained L_2-L_p Minimization Complexity of Unconstrained L_2-L_p Minimization

2011-05-03

arxiv.org/abs/1105.0638v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Complexity of Unconstrained L_2-L_p Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity of Unconstrained L_2-L_p Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Unconstrained L_2-L_p Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-694252