Optimization Online


Cyclic Coordinate Update Algorithms for Fixed-Point Problems: Analysis and Applications

Yat Tin Chow (ytchow***at***math.ucla.edu)
Tianyu Wu (wuty11***at***math.ucla.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: Many problems reduce to the fixed-point problem of solving $x=T(x)$. To this problem, we apply the coordinate-update algorithms, which update only one or a few components of $x$ at each step. When each update is cheap, these algorithms are faster than the full fixed-point iteration (which updates all the components). In this paper, we focus on the coordinate-update algorithms based on the cyclic selection rules, where the ordering of coordinates in each cycle is arbitrary. These algorithms are fast, but their convergence is unknown in the fixed-point setting. When $T$ is a nonexpansive operator and has a fixed point, we show that the sequence of coordinate-update iterates converges to a fixed point under proper step sizes. This result applies to the primal-dual coordinate-update algorithms, which have applications to optimization problems with nonseparable nonsmooth objectives, as well as global linear constraints. Numerically, we apply coordinate-update algorithms with the cyclic, shuffled cyclic, and random selection rules to $\ell_1$ robust least squares, a CT image reconstruction problem, as well as nonnegative matrix factorization. They converge much faster than the standard fixed-point iteration. Among the three rules, cyclic and shuffled cyclic rules are overall faster than the random rule.

Keywords: coordinate update, cyclic, shuffled cyclic, fixed point, nonexpansive operator, robust least squares, image reconstruction, nonnegative matrix factorization

Category 1: Convex and Nonsmooth Optimization

Citation: UCLA CAM Report 16-78

Download: [PDF]

Entry Submitted: 11/08/2016
Entry Accepted: 11/08/2016
Entry Last Modified: 03/02/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society