Journal article
A Unified Primal Dual Active Set Algorithm for Nonconvex Sparse Recovery
Statistical science, Vol.36(2), pp.215-238
05/01/2021
DOI: 10.1214/19-STS758
Abstract
In this paper, we consider the problem of recovering a sparse signal based on penalized least squares formulations. We develop a novel algorithm of primal-dual active set type for a class of nonconvex sparsitypromoting penalties, including l(0), bridge, smoothly clipped absolute deviation, capped l(1) and minimax concavity penalty. First, we establish the existence of a global minimizer for the related optimization problems. Then we derive a novel necessary optimality condition for the global minimizer using the associated thresholding operator. The solutions to the optimality system are coordinatewise minimizers, and under minor conditions, they are also local minimizers. Upon introducing the dual variable, the active set can be determined using the primal and dual variables together. Further, this relation lends itself to an iterative algorithm of active set type which at each step involves first updating the primal variable only on the active set and then updating the dual variable explicitly. When combined with a continuation strategy on the regularization parameter, the primal dual active set method is shown to converge globally to the underlying regression target under certain regularity conditions. Extensive numerical experiments with both simulated and real data demonstrate its superior performance in terms of computational efficiency and recovery accuracy compared with the existing sparse recovery methods.
Details
- Title: Subtitle
- A Unified Primal Dual Active Set Algorithm for Nonconvex Sparse Recovery
- Creators
- Jian Huang - University of IowaYuling Jiao - Zhongnan University of Economics and LawBangti Jin - University College LondonJin Liu - National University of SingaporeXiliang Lu - Wuhan UniversityCan Yang - Hong Kong University of Science and Technology
- Resource Type
- Journal article
- Publication Details
- Statistical science, Vol.36(2), pp.215-238
- DOI
- 10.1214/19-STS758
- ISSN
- 0883-4237
- eISSN
- 2168-8745
- Publisher
- INST MATHEMATICAL STATISTICS-IMS
- Number of pages
- 24
- Grant note
- R9405 / Hong Kong University of Science and Technology 91630313; 11871385; 11871474; 61701547 / National Science Foundation of China; National Natural Science Foundation of China (NSFC) WBS: R-913200-098-263 / Duke-NUS Graduate Medical School; National University of Singapore 61501389 / National Science Funding of China 22302815; 12316116; 12301417 / Hong Kong Research Grant Council; Hong Kong Research Grants Council 2018YFC1314600 / National Key Research and Development Program of China MOE2016-T2-2-029 / Ministry of Eduction, Singapore KLATASDSMOE EP/M025160/1; EP/T000864/1 / UK EPSRC; UK Research & Innovation (UKRI); Engineering & Physical Sciences Research Council (EPSRC) DMS-1916199 / NSF; National Science Foundation (NSF) 2019CFA007 / Natural Science Foundation of Hubei Province; Natural Science Foundation of Hubei Province
- Language
- English
- Date published
- 05/01/2021
- Academic Unit
- Statistics and Actuarial Science
- Record Identifier
- 9984257735702771
Metrics
21 Record Views