  


Cyclic Coordinate Update Algorithms for FixedPoint Problems: Analysis and Applications
Yat Tin Chow (ytchowmath.ucla.edu) Abstract: Many problems reduce to the fixedpoint problem of solving $x=T(x)$. To this problem, we apply the coordinateupdate 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 fixedpoint iteration (which updates all the components). In this paper, we focus on the coordinateupdate 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 fixedpoint setting. When $T$ is a nonexpansive operator and has a fixed point, we show that the sequence of coordinateupdate iterates converges to a fixed point under proper step sizes. This result applies to the primaldual coordinateupdate algorithms, which have applications to optimization problems with nonseparable nonsmooth objectives, as well as global linear constraints. Numerically, we apply coordinateupdate 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 fixedpoint 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 1678 Download: [PDF] Entry Submitted: 11/08/2016 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  