Paper Info
Title
A coordinate descent homotopy method for linearly constrained nonsmooth convex minimization
Abstract
A problem in optimization, with a wide range of applications, entails finding a solution of a linear equation <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"goms_a_1088851_ilm0001.gif\"/</inline-formula> with various minimization properties. Such applications include compressed sensing, which requires an efficient method to find a minimal <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"goms_a_1088851_ilm0002.gif\"/</inline-formula> norm solution. We propose a coordinate descent homotopy method to solve the linearly constrained convex minimization problem <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"goms_a_1088851_ilm0003.gif\"/</inline-formula> where P is proper, convex and lower semicontinuous. A well-known special case is the basis pursuit problem <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"goms_a_1088851_ilm0004.gif\"/</inline-formula>. The greedy-type coordinate descent method is applied to solve the regularized linear least squares problem, which arises as a sequence of subproblems for the proposed method, and we show global linear convergence. We report numerical results for solving large-scale basis pursuit problem. Comparison with Bregman iterative algorithm [W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"goms_a_1088851_ilm0005.gif\"/</inline-formula>-minimization with applications to compressed sensing, SIAM J. Image Sci. 1 2008, pp. 143–168] and linearized Bregman iterative algorithm [J.-F. Cai, S. Osher, and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comput. 78 2009, pp. 1515–1536] suggests that the proposed method can be used as an efficient method for <inline-formula><inline-graphic xmlns:xlink=\"http://www.w3.org/1999/xlink\" xlink=\"goms_a_1088851_ilm0006.gif\"/</inline-formula> minimization problem.
Year
DOI
Venue
2016
10.1080/10556788.2015.1088851
Optimization Methods and Software
Keywords
Field
DocType
homotopy method,coordinate descent method,linearly constrained nonsmooth convex minimization,49M27,65K05,90C06,90C25,90C30
Mathematical optimization,Iterative method,Basis pursuit,Random coordinate descent,Rate of convergence,Bregman divergence,Coordinate descent,Convex optimization,Linear least squares,Mathematics
Journal
Volume
Issue
ISSN
31
2
1055-6788
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Yoon Mo Jung1586.09
Sangwoon Yun250742.38