On the Convergence of an Active Set Method for L1 Minimization

We analyze an abridged version of the active-set algorithm FPC_AS for solving the L1-regularized least squares problem. The active set algorithm alternatively iterates between two stages. In the first "nonmonotone 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 nonzero components of the solution 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 of 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