Name
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 l1-regularized problem, i.e. a weighted sum of the l1-norm |x|1 and a smooth function fx. 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1080/10556788.2011.591398 | Optimization Methods and Software |
Keywords | Field | DocType |
siam j. sci,active-set method,subspace optimisation,smaller smooth problem,l1-regularized problem,global convergence,smooth function fx,fast algorithm,convergence rate,active-set algorithm,subspace optimization,active set method,line search,compressed sensing,first order,basis pursuit,continuation | Convergence (routing),Mathematical optimization,Finite set,Subspace topology,Active set method,Line search,Stationary point,Rate of convergence,Iterated function,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 6 | 1055-6788 |
Citations | PageRank | References |
15 | 0.71 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zaiwen Wen | 1 | 934 | 40.20 |
| Wotao Yin | 2 | 5038 | 243.92 |
| Hongchao Zhang | 3 | 809 | 43.29 |
| Donald Goldfarb | 4 | 868 | 72.71 |