Speaker: Professor Yinyu Ye (Stanford University)

Inviter: Center of Optimization and Applications

Time: September 1 (Thursday), 9:00-10:00

Venue: Room 311

Topic: Complexity of Unconstrained L_2-L_p Minimization

Abstract: 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.