A Fast Active Set Block Coordinate Descent Algorithm for ${\ell }_1$-regularized least squares

Abstract

The problem of finding sparse solutions to underdetermined systems of linear equations arises in several applications (e.g. signal and image processing, compressive sensing, statistical inference). A standard tool for dealing with sparse recovery is the ${\ell }_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 satisfied. A relevant feature of the estimate is that it gives a significant reduction of the objective function when setting to zero all those variables estimated active. This enables to easily embed it into a given globally converging algorithmic framework. In particular, we include our estimate into a block coordinate descent algorithm for ${\ell }_1$-regularized least squares, analyze the convergence properties of this new active set method, and prove that its basic version converges with linear rate. Finally, we report some numerical results showing the effectiveness of the approach.

28 pages, 5 figures

Cited by in corpus (9)

• Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
• A Two-Stage Active-Set Algorithm for Bound-Constrained Optimization
• "Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?
• Dual Extrapolation for Sparse Generalized Linear Models
• An Active-Set Algorithmic Framework for Non-Convex Optimization Problems over the Simplex
• A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization
• Carathéodory Sampling for Stochastic Gradient Descent
• Minimization over the l1-ball using an active-set non-monotone projected gradient
• Second-order orthant-based methods with enriched Hessian information for sparse ${\ell }_1$-optimization