Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency

DOI10.1137/23m1567503arXiv2207.04291MaRDI QIDQ6130543

Deren Han, Yansheng Su, Jiaxin Xie

Publication date: 3 April 2024

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2207.04291

zbMATH Keywords

linear systemsrandomizationconvergence rateKaczmarz methodDouglas-Rachfordheavy ball momentum

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Convex programming (90C25) Iterative numerical methods for linear systems (65F10) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Linear and strong convergence of algorithms involving averaged nonexpansive operators
• Greedy and randomized versions of the multiplicative Schwarz method
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Convergence of a randomized Douglas-Rachford method for linear system
• A randomized Kaczmarz algorithm with exponential convergence
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the convergence of von Neumann's alternating projection algorithm for two sets
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• Random activations in primal-dual splittings for monotone inclusions with a priori information
• A survey on some recent developments of alternating direction method of multipliers
• Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
• Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
• A cyclic Douglas-Rachford iteration scheme
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• First-order and stochastic optimization methods for machine learning
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
• On the rate of convergence of the alternating projection method in finite dimensional spaces
• New Douglas--Rachford Algorithmic Structures and Their Convergence Analyses
• Randomized Extended Kaczmarz for Solving Least Squares
• The Douglas–Rachford Algorithm in the Absence of Convexity
• Iterative Methods for Linear Systems
• Projection Methods: Swiss Army Knives for Solving Feasibility and Best Approximation Problems with Halfspaces
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• An Algorithm for Restricted Least Squares Regression
• An accelerated randomized Kaczmarz algorithm
• Randomized Iterative Methods for Linear Systems
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• A unified treatment of some iterative algorithms in signal processing and image reconstruction
• Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization
• Preasymptotic convergence of randomized Kaczmarz method
• On Greedy Randomized Kaczmarz Method for Solving Large Sparse Linear Systems
• A weighted randomized Kaczmarz method for solving linear systems
• Convergence analyses based on frequency decomposition for the randomized row iterative method
• Randomized Kaczmarz Converges Along Small Singular Vectors
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Surrounding the solution of a linear system of equations from all sides
• On Adaptive Sketch-and-Project for Solving Linear Systems
• Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols
• Adaptively sketched Bregman projection methods for linear systems
• The Douglas--Rachford Algorithm Converges Only Weakly
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
• Analyzing random permutations for cyclic coordinate descent
• Randomized Extended Average Block Kaczmarz for Solving Least Squares
• Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems
• Faster Randomized Block Kaczmarz Algorithms
• Stochastic Gradient Descent for Linear Systems with Missing Data
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression
• The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators
• Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
• Some methods of speeding up the convergence of iteration methods
• Linear Recursive Sequences
• A Stochastic Approximation Method
• A Deterministic Kaczmarz Algorithm for Solving Linear Systems

This page was built for publication: Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency