Complexity of unconstrained L2-Lp minimization

Xiaojun Chen, Dongdong Ge, Zizhuo Wang, Yinyu Ye

Research output: Journal article publicationJournal articleAcademic researchpeer-review

96 Citations (Scopus)


We consider the unconstrained Lq - Lp minimization: find a minimizer of ∥Ax-b∥qq+λ∥x∥ pp for given A ∈ Rm×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 L2-Lp 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 Lq - Lp problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function ∥̇∥pp. In this paper, we show that the L q - Lp 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.
Original languageEnglish
Pages (from-to)371-383
Number of pages13
JournalMathematical Programming
Issue number1-2
Publication statusPublished - 1 Feb 2014


  • Bridge estimator
  • Nonconvex optimization
  • Nonsmooth optimization
  • Sparse solution reconstruction
  • Variable selection

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Complexity of unconstrained L2-Lp minimization'. Together they form a unique fingerprint.

Cite this