A coordinate descent homotopy method for linearly constrained nonsmooth convex minimization

摘要

A problem in optimization, with a wide range of applications, entails finding a solution of a linear equation Ax = b with various minimization properties. Such applications include compressed sensing, which requires an efficient method to find a minimal l(1) norm solution. We propose a coordinate descent homotopy method to solve the linearly constrained convex minimization problem min{P(x) vertical bar Ax = b, x is an element of R-n} where P is proper, convex and lower semicontinuous. A well-known special case is the basis pursuit problem min{parallel to x(1)parallel to vertical bar Ax = b, x is an element of R-n}. 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 l(1)-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. 15151536] suggests that the proposed method can be used as an efficient method for l(1) minimization problem.