Uniqueness of DRS as the 2 Operator Resolvent-Splitting and\n Impossibility of 3 Operator Resolvent-Splitting

2018/01/01 by Ernest K. Ryu, Ryu, Ernest K. · 7 citations
Computer Science · Mathematics · #Matrix Theory and Algorithms #Mathematical Analysis and Transform Methods #Advanced Operator Algebra Research

paper · pdf · doi:10.48550/arxiv.1802.07534

Abstract

Given the success of Douglas--Rachford splitting (DRS), it is natural to ask\nwhether DRS can be generalized. Are there other 2 operator resolvent-splittings\nsharing the favorable properties of DRS? Can DRS be generalized to 3 operators?\nThis work presents the answers: no and no. In a certain sense, DRS is the\nunique 2 operator resolvent-splitting, and generalizing DRS to 3 operators is\nimpossible without lifting, where lifting roughly corresponds to enlarging the\nproblem size. The impossibility result further raises a question. How much\nlifting is necessary to generalize DRS to 3 operators? This work presents the\nanswer by providing a novel 3 operator resolvent-splitting with provably\nminimal lifting that directly generalizes DRS.\n

Citations

• Splitting Algorithms for the Sum of Two Nonlinear Operators

Cited by

• Primal-dual splitting for structured composite monotone inclusions with or without cocoercivity
• Extending Douglas-Rachford Splitting for Convex Optimization
• Resolvent Splitting for Sums of Monotone Operators with Minimal Lifting
• Bregman Douglas-Rachford Splitting Method
• Frugal forward-backward splitting methods with deviations
• Relocated Fixed-Point Iterations with Applications to Variable Stepsize Resolvent Splitting
• Preconditioned Halpern iteration with adaptive anchoring parameters and an acceleration to Chambolle-Pock algorithm
• Graph splitting methods: Fixed points and strong convergence for linear subspaces

Related

• A Note on the Forward-Douglas--Rachford Splitting for Monotone Inclusion\n and Convex Optimization
• A note on the equivalence of operator splitting methods
• Strengthened Splitting Methods for Computing Resolvents
• A Three-Operator Splitting Scheme and its Optimization Applications
• Resolvent Splitting for Sums of Monotone Operators with Minimal Lifting