![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
Abstract
We analyse an abridged version of the active-set algorithm FPC_AS proposed in Wen et al. [A fast algorithm for sparse reconstruction based on shrinkage, subspace optimisation and continuation, SIAM J. Sci. Comput. 32 (2010), pp. 1832–1857] for solving the l 1-regularized problem, i.e. a weighted sum of the l 1-norm |x|1 and a smooth function f(x). The active-set algorithm alternatively iterates between two stages. In the first ‘non-monotone line search (NMLS)’ stage, an iterative first-order method based on ‘shrinkage’ is used to estimate the support at the solution. In the second ‘subspace optimization’ stage, a smaller smooth problem is solved to recover the magnitudes of the non-zero components of x. We show that NMLS itself is globally convergent and the convergence rate is at least R-linearly. In particular, NMLS is able to identify the zero components of a stationary point after a finite number of steps under some mild conditions. The global convergence of FPC_AS is established based on the properties of NMLS.
Acknowledgements
The authors are grateful to the Associate Editor and two anonymous referees for their detailed and valuable comments and suggestions. Z. Wen's research was supported in part by NSF DMS-0439872 through UCLA IPAM. W. Yin's research was supported in part by NSF CAREER Award DMS-07-48839, ONR Grant N00014-08-1-1101, U.S. ARL and ARO grant W911NF-09-1-0383 and an Alfred P. Sloan Research Fellowship. H. Zhang's research was supported in part by NSF DMS-1016204. D. Goldfarb's research was supported in part by NSF Grant DMS 10-16571, ONR Grant N00014-8-1-1118 and DOE Grant DE-FG02-08-25856.