Randomized Douglas-Rachford methods for linear systems: Improved accuracy and efficiency

The Douglas-Rachford (DR) method is a widely used method for finding a pointin the intersection of two closed convex sets (feasibility problem). However,the method converges weakly and the associated rate of convergence is hard toanalyze in general. In addition, the direct extension of the DR method forsolving more-than-two-sets feasibility problems, called the $r$-sets-DR method,is not necessarily convergent. To improve the efficiency of the optimizationalgorithms, the introduction of randomization and the momentum technique hasattracted increasing attention. In this paper, we propose the randomized$r$-sets-DR (RrDR) method for solving the feasibility problem derived fromlinear systems, showing the benefit of the randomization as it brings linearconvergence in expectation to the otherwise divergent $r$-sets-DR method.Furthermore, the convergence rate does not depend on the dimension of thecoefficient matrix. We also study RrDR with heavy ball momentum and establishits accelerated rate. Numerical experiments are provided to confirm our resultsand demonstrate the notable improvements in accuracy and efficiency of the DRmethod, brought by the randomization and the momentum technique.