Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/23856
Title: Complexity of unconstrained L2-Lp minimization
Authors: Chen, X 
Ge, D
Wang, Z
Ye, Y 
Keywords: Bridge estimator
Nonconvex optimization
Nonsmooth optimization
Sparse solution reconstruction
Variable selection
Issue Date: 2014
Source: Mathematical programming, 2014, v. 143, no. 1-2, p. 371-383 How to cite?
Journal: Mathematical Programming 
Abstract: We consider the unconstrained Lq - Lp minimization: find a minimizer of ∥Ax-b∥q q+λ∥x∥ p p 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 ∥̇∥p p. 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.
URI: http://hdl.handle.net/10397/23856
ISSN: 0025-5610
DOI: 10.1007/s10107-012-0613-0
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

22
Last Week
0
Last month
1
Citations as of Aug 17, 2017

WEB OF SCIENCETM
Citations

17
Last Week
1
Last month
1
Citations as of Aug 15, 2017

Page view(s)

41
Last Week
5
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.