Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/6032
Title: Lower bound theory of nonzero entries in solutions of l ₂-l [sub p] minimization
Authors: Chen, X 
Xu, F
Ye, Y
Keywords: Variable selection
Sparse solution
Linear least-squares problem
l [sub p] regularization
Smoothing approximation
First order condition
Second order condition
Issue Date: 2010
Publisher: Society for Industrial and Applied Mathematics
Source: SIAM journal on scientific computing, v. 32, no. 5, p. 2832–2852 How to cite?
Journal: SIAM journal on scientific computing 
Abstract: Recently, variable selection and sparse reconstruction are solved by finding an optimal solution of a minimization model, where the objective function is the sum of a data-fitting term in l₂ norm and a regularization term in l [sub p] norm (0<p<1). Since it is a nonconvex model, most algorithms for solving the problem can provide only an approximate local optimal solution, where nonzero entries in the solution cannot be identified theoretically. In this paper, we establish lower bounds for the absolute value of nonzero entries in every local optimal solution of the model, which can be used to indentify zero entries precisely in any numerical solution. Therefore, we have developed a lower bound theorem to classify zero and nonzero entries in every local solution. These lower bounds clearly show the relationship between the sparsity of the solution and the choice of the regularization parameter and norm so that our theorem can be used for selecting desired model parameters and norms. Furthermore, we also develop error bounds for verifying the accuracy of numerical solutions of the l₂-l [sub p] minimization model. To demonstrate applications of our theory, we propose a hybrid orthogonal matching pursuit-smoothing gradient (OMP-SG) method for solving the nonconvex, non-Lipschitz continuous l₂-l [sub p] minimization problem. Computational results show the effectiveness of the lower bounds for identifying nonzero entries in numerical solutions and the OMP-SG method for finding a high quality numerical solution.
URI: http://hdl.handle.net/10397/6032
ISSN: 1064-8275
EISSN: 1095-7197
DOI: 10.1137/090761471
Rights: © 2010 Society for Industrial and Applied Mathematics
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
Chen_Lower_Bound_Theory.pdf345.38 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

88
Last Week
3
Last month
2
Citations as of Oct 12, 2017

WEB OF SCIENCETM
Citations

86
Last Week
1
Last month
1
Citations as of Oct 18, 2017

Page view(s)

157
Last Week
1
Last month
Checked on Oct 23, 2017

Download(s)

282
Checked on Oct 23, 2017

Google ScholarTM

Check

Altmetric



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