  


A Coordinate Gradient Descent Method for L_1regularized Convex Minimization
Sangwoon Yun (matysnus.edu.sg) Abstract: In applications such as signal processing and statistics, many problems involve finding sparse solutions to underdetermined linear systems of equations. These problems can be formulated as a structured nonsmooth optimization problems, i.e., the problem of minimizing L_1regularized 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 L_1regularized convex smooth function. We establish a Qlinear convergence rate for our method when the coordinate block is chosen by a GaussSouthwelltype rule to ensure sufficient descent. We propose efficient implementations of the CGD method and report numerical results for solving largescale L_1regularized linear least squares problems arising in compressed sensing and image deconvolution as well as largescale L_1regularized logistic regression problems for feature selection in data classification. Comparison with several stateoftheart algorithms specifically designed for solving largescale L_1regularized 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. Keywords: Coordinate gradient descent, Qlinear convergence, L_1regularization, compressed sensing, image deconvolution, linear least squares, logistic regression, convex optimization Category 1: Convex and Nonsmooth Optimization Citation: Pacific J. Optimization, 6 (2010), pp. 615640. Download: [PDF] Entry Submitted: 04/23/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  