Please use this identifier to cite or link to this item:
Title: A coordinate gradient descent method for l1-regularized convex minimization
Authors: Yun, S. 
Toh, K.-C.
Keywords: Compressed sensing
Convex optimization
Coordinate gradient descent
Image deconvolution
L1- Regularization
Linear least squares
Logistic regression
Q-linear convergence
Issue Date: Mar-2011
Citation: Yun, S., Toh, K.-C. (2011-03). A coordinate gradient descent method for l1-regularized convex minimization. Computational Optimization and Applications 48 (2) : 273-307. ScholarBank@NUS Repository.
Abstract: In applications such as signal processing and statistics, many problems involve finding sparse solutions to under-determined linear systems of equations. These problems can be formulated as a structured nonsmooth optimization problems, i.e., the problem of minimizing l1regularized linear least squares problems. In this paper, we propose a block coordinate gradient descent method (abbreviated as CGD) to solve the more general l 1regularized convex minimization problems, i.e., the problem of minimizing an l1regularized convex smooth function. We establish a Q-linear convergence rate for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We propose efficient implementations of the CGD method and report numerical results for solving large-scale l1regularized linear least squares problems arising in compressed sensing and image deconvolution as well as large-scale l 1regularized logistic regression problems for feature selection in data classification. Comparison with several state-of-the-Art algorithms specifically designed for solving large-scale l1regularized linear least squares or logistic regression problems suggests that an efficiently implemented CGD method may outperform these algorithms despite the fact that the CGD method is not specifically designed just to solve these special classes of problems. © Springer Science+Business Media, LLC 2009.
Source Title: Computational Optimization and Applications
ISSN: 09266003
DOI: 10.1007/s10589-009-9251-8
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 20, 2022


checked on Nov 11, 2022

Page view(s)

checked on Nov 24, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.