A fast active set block coordinate descent algorithm for ℓ1-regularized least squares

The problem of nding sparse solutions to underdetermined systems of linear equa- tions arises in several applications (e.g., signal and image processing, compressive sensing, statistical inference). A standard tool for dealing with sparse recovery is the L-1 regularized least squares approach that has been recently attracting the attention of many researchers. In this paper, we describe an active set estimate (i.e., an estimate of the indices of the zero variables in the optimal solution) for the considered problem that tries to quickly identify as many active variables as possible at a given point, while guaranteeing that some approximate optimality conditions are satis ed. A rele- vant feature of the estimate is that it gives a signi cant reduction of the objective function when setting to zero all those variables estimated to be active. This enables us to easily embed it into a given globally converging algorithmic framework. In particular, we include our estimate into a block coordinate descent algorithm for ` 1 -regularized least squares, analyze the convergence properties of this new active set method, and prove that its basic version converges with a linear rate. Finally, we report some numerical results showing the e ectiveness of the approach