Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Gradient-based method with active set strategy for $ \ell_1$ optimization


Authors: Wanyou Cheng and Yu-Hong Dai
Journal: Math. Comp. 87 (2018), 1283-1305
MSC (2010): Primary 90C06, 90C25, 65Y20, 94A08
DOI: https://doi.org/10.1090/mcom/3238
Published electronically: August 3, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we propose an identification function and develop an active set identification technique for solving the $ \ell _1$ optimization problem. Such a technique has a strong ability to accurately identify the zero components in a neighbourhood of an isolated stationary point without strict complementarity conditions. Based on the active set identification technique, we propose a gradient-based method for the $ \ell _1$ optimization problem. To accelerate the algorithm, a subspace Barzilai-Borwein steplength and a subspace exact steplength are developed, respectively. Under appropriate conditions, we show that the method with the nonmonotone line search technique is globally convergent. Numerical experiments with compressive sensing problems show that our approach is competitive with several known methods for the standard $ \ell _2$-$ \ell _1$ problem.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C06, 90C25, 65Y20, 94A08

Retrieve articles in all journals with MSC (2010): 90C06, 90C25, 65Y20, 94A08


Additional Information

Wanyou Cheng
Affiliation: College of Computer, Dongguan University of Technology, Dongguan 523000, People’s Republic of China
Email: chengwanyou@sina.com

Yu-Hong Dai
Affiliation: LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, People’s Republic of China
Email: dyh@lsec.cc.ac.cn

DOI: https://doi.org/10.1090/mcom/3238
Keywords: $\ell_1$ minimization, compressive sensing, active set, Barzilai-Borwein method
Received by editor(s): November 28, 2014
Received by editor(s) in revised form: October 4, 2015, July 30, 2016, and October 23, 2016
Published electronically: August 3, 2017
Additional Notes: The authors were supported by the Chinese NSF Grant (nos. 11371154, 11331012 and 81173633), the Key Project of Chinese National Programs for Fundamental Research and Development (no. 2015CB856000), the China National Funds for Distinguished Young Scientists (no. 11125107) and by the Guangdong Province Outstanding Young Teacher Training Program (nos. 3XZ150603 and 2015KTSCX1)
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society