December  2020, 10(4): 463-474. doi: 10.3934/naco.2020045

Convergence of a randomized Douglas-Rachford method for linear system

School of Mathematical Sciences, Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing, 210023, China

Received  March 2020 Revised  September 2020 Published  September 2020

Fund Project: The research of the second author is partially supported by the NSFC grants 11871279, 11571178

In this article, we propose a randomized Douglas-Rachford(DR) method for linear system. This algorithm is based on the cyclic DR method. We consider a linear system as a feasible problem of finding intersection of hyperplanes. In each iteration, the next iteration point is determined by a random DR operator. We prove the convergence of the iteration points based on expectation. And the variance of the iteration points declines to zero. The numerical experiment shows that the proposed algorithm performs better than the cyclic DR method.

Citation: Leyu Hu, Xingju Cai. Convergence of a randomized Douglas-Rachford method for linear system. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 463-474. doi: 10.3934/naco.2020045
References:
[1]

Z.-Z. Bai and W.-T. Wu, On convergence rate of the randomized kaczmarz method, Linear Algebra and Its Applications, 553 (2018), 252-269.  doi: 10.1016/j.laa.2018.05.009.  Google Scholar

[2]

Z.-Z. Bai and W.-T. Wu, On greedy randomized kaczmarz method for solving large sparse linear systems, SIAM Journal on Scientific Computing, 40 (2018), A592–A606. doi: 10.1137/17M1137747.  Google Scholar

[3]

H. H. Bauschke, Projection algorithms: results and open problems, in Studies in Computational Mathematics, Elsevier, 8 (2001), 11–22. doi: 10.1016/S1570-579X(01)80003-3.  Google Scholar

[4]

H. H. Bauschke and J. M. Borwein, On the convergence of von neumann's alternating projection algorithm for two sets, Set-Valued Analysis, 1 (1993), 185-212.  doi: 10.1007/BF01027691.  Google Scholar

[5]

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367-426.  doi: 10.1137/S0036144593251710.  Google Scholar

[6]

H. H. BauschkeJ. M. Borwein and A. S. Lewis, The method of cyclic projections for closed convex sets in hilbert space, Contemporary Mathematics, 204 (1997), 1-38.  doi: 10.1090/conm/204/02620.  Google Scholar

[7]

H. H. Bauschke, P. L. Combettes et al., Convex Analysis and Monotone Operator Theory in Hilbert Spaces, vol. 408, Springer, 2011. doi: 10.1007/978-1-4419-9467-7.  Google Scholar

[8]

J. M. Borwein and M. K. Tam, A cyclic douglas–rachford iteration scheme, Journal of Optimization Theory and Applications, 160 (2014), 1-29.  doi: 10.1007/s10957-013-0381-x.  Google Scholar

[9]

J. P. Boyle and R. L. Dykstra, A method for finding projections onto the intersection of convex sets in hilbert spaces, in Advances in order restricted statistical inference, Springer, (1986), 28–47. doi: 10.1007/978-1-4613-9940-7_3.  Google Scholar

[10]

C. Brezinski, Projection methods for linear systems, Journal of Computational and Applied Mathematics, 77 (1997), 35-51.  doi: 10.1016/S0377-0427(96)00121-5.  Google Scholar

[11]

J. Douglas and H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables, Transactions of the American mathematical Society, 82 (1956), 421-439.  doi: 10.2307/1993056.  Google Scholar

[12]

R. L. Dykstra, An algorithm for restricted least squares regression, Journal of the American Statistical Association, 78 (1983), 837-842.   Google Scholar

[13]

T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numerische Mathematik, 35 (1980), 1-12.  doi: 10.1007/BF01396365.  Google Scholar

[14]

M. Griebel and P. Oswald, Greedy and randomized versions of the multiplicative schwarz method, Linear Algebra and Its Applications, 437 (2012), 1596-1610.  doi: 10.1016/j.laa.2012.04.052.  Google Scholar

[15]

S. Karczmarz, Angenäherte auflösung von systemen linearer gleichungen, Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, 35 (1937), 355-357.   Google Scholar

[16]

D. NeedellR. Zhao and A. Zouzias, Randomized block kaczmarz method with projection for solving least squares, Linear Algebra and its Applications, 484 (2015), 322-343.  doi: 10.1016/j.laa.2015.06.027.  Google Scholar

[17]

J. Nutini, B. Sepehry, I. Laradji, M. Schmidt, H. Koepke and A. Virani, Convergence rates for greedy kaczmarz algorithms, and faster randomized kaczmarz rules using the orthogonality graph, in Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, AUAI Press, (2016), 547–556. Google Scholar

[18]

T. Strohmer and R. Vershynin, A randomized kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications, 15 (2008), 262. doi: 10.1007/s00041-008-9030-4.  Google Scholar

[19]

J. Von Neumann, The geometry of orthogonal spaces, Functional operators-vol. II, Annals of Mathematics Studies, 22 (1950), This is a reprint of mimeographed lecture notes, first distributed in 1933.  Google Scholar

show all references

References:
[1]

Z.-Z. Bai and W.-T. Wu, On convergence rate of the randomized kaczmarz method, Linear Algebra and Its Applications, 553 (2018), 252-269.  doi: 10.1016/j.laa.2018.05.009.  Google Scholar

[2]

Z.-Z. Bai and W.-T. Wu, On greedy randomized kaczmarz method for solving large sparse linear systems, SIAM Journal on Scientific Computing, 40 (2018), A592–A606. doi: 10.1137/17M1137747.  Google Scholar

[3]

H. H. Bauschke, Projection algorithms: results and open problems, in Studies in Computational Mathematics, Elsevier, 8 (2001), 11–22. doi: 10.1016/S1570-579X(01)80003-3.  Google Scholar

[4]

H. H. Bauschke and J. M. Borwein, On the convergence of von neumann's alternating projection algorithm for two sets, Set-Valued Analysis, 1 (1993), 185-212.  doi: 10.1007/BF01027691.  Google Scholar

[5]

H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367-426.  doi: 10.1137/S0036144593251710.  Google Scholar

[6]

H. H. BauschkeJ. M. Borwein and A. S. Lewis, The method of cyclic projections for closed convex sets in hilbert space, Contemporary Mathematics, 204 (1997), 1-38.  doi: 10.1090/conm/204/02620.  Google Scholar

[7]

H. H. Bauschke, P. L. Combettes et al., Convex Analysis and Monotone Operator Theory in Hilbert Spaces, vol. 408, Springer, 2011. doi: 10.1007/978-1-4419-9467-7.  Google Scholar

[8]

J. M. Borwein and M. K. Tam, A cyclic douglas–rachford iteration scheme, Journal of Optimization Theory and Applications, 160 (2014), 1-29.  doi: 10.1007/s10957-013-0381-x.  Google Scholar

[9]

J. P. Boyle and R. L. Dykstra, A method for finding projections onto the intersection of convex sets in hilbert spaces, in Advances in order restricted statistical inference, Springer, (1986), 28–47. doi: 10.1007/978-1-4613-9940-7_3.  Google Scholar

[10]

C. Brezinski, Projection methods for linear systems, Journal of Computational and Applied Mathematics, 77 (1997), 35-51.  doi: 10.1016/S0377-0427(96)00121-5.  Google Scholar

[11]

J. Douglas and H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables, Transactions of the American mathematical Society, 82 (1956), 421-439.  doi: 10.2307/1993056.  Google Scholar

[12]

R. L. Dykstra, An algorithm for restricted least squares regression, Journal of the American Statistical Association, 78 (1983), 837-842.   Google Scholar

[13]

T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numerische Mathematik, 35 (1980), 1-12.  doi: 10.1007/BF01396365.  Google Scholar

[14]

M. Griebel and P. Oswald, Greedy and randomized versions of the multiplicative schwarz method, Linear Algebra and Its Applications, 437 (2012), 1596-1610.  doi: 10.1016/j.laa.2012.04.052.  Google Scholar

[15]

S. Karczmarz, Angenäherte auflösung von systemen linearer gleichungen, Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, 35 (1937), 355-357.   Google Scholar

[16]

D. NeedellR. Zhao and A. Zouzias, Randomized block kaczmarz method with projection for solving least squares, Linear Algebra and its Applications, 484 (2015), 322-343.  doi: 10.1016/j.laa.2015.06.027.  Google Scholar

[17]

J. Nutini, B. Sepehry, I. Laradji, M. Schmidt, H. Koepke and A. Virani, Convergence rates for greedy kaczmarz algorithms, and faster randomized kaczmarz rules using the orthogonality graph, in Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, AUAI Press, (2016), 547–556. Google Scholar

[18]

T. Strohmer and R. Vershynin, A randomized kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications, 15 (2008), 262. doi: 10.1007/s00041-008-9030-4.  Google Scholar

[19]

J. Von Neumann, The geometry of orthogonal spaces, Functional operators-vol. II, Annals of Mathematics Studies, 22 (1950), This is a reprint of mimeographed lecture notes, first distributed in 1933.  Google Scholar

Figure 1.  Comparison of number of projections/reflections between randomized Kaczmarz(RK), cyclic DR(CDR) and randomized DR(RDR) when the size of $ A $ and $ b $ is $ m = 1000 $ and $ n = 100 $
Table 1.  Number of Projections/Reflections(NPR) for $ n = 50 $
$ m $ $ 1000 $ $ 2000 $ $ 3000 $ $ 4000 $ $ 5000 $
NPR CDR 1264 1404 1282 1488 1390
RK 725.3 701.1 696.1 671.3 683.8
RDR 705.2 683.8 696 669.6 698.8
$ m $ $ 1000 $ $ 2000 $ $ 3000 $ $ 4000 $ $ 5000 $
NPR CDR 1264 1404 1282 1488 1390
RK 725.3 701.1 696.1 671.3 683.8
RDR 705.2 683.8 696 669.6 698.8
Table 2.  Number of Projections/Reflections(NPR) for $ n = 100 $
$ m $ $ 1000 $ $ 2000 $ $ 3000 $ $ 4000 $ $ 5000 $
NPR CDR 2620 2604 2692 2770 2770
RK 1508.4 1419 1425.5 1422.5 1395.1
RDR 1523.2 1425.8 1409.6 1421.4 1381.8
$ m $ $ 1000 $ $ 2000 $ $ 3000 $ $ 4000 $ $ 5000 $
NPR CDR 2620 2604 2692 2770 2770
RK 1508.4 1419 1425.5 1422.5 1395.1
RDR 1523.2 1425.8 1409.6 1421.4 1381.8
Table 3.  Number of Projections/Reflections(NPR) for $ n = 150 $
$ m $ $ 1000 $ $ 2000 $ $ 3000 $ $ 4000 $ $ 5000 $
NPR CDR 4272 4286 4104 4096 3854
RK 2466.9 2194.4 2175.4 2092.1 2152
RDR 2574.2 2227.8 2160.8 2133 2113.8
$ m $ $ 1000 $ $ 2000 $ $ 3000 $ $ 4000 $ $ 5000 $
NPR CDR 4272 4286 4104 4096 3854
RK 2466.9 2194.4 2175.4 2092.1 2152
RDR 2574.2 2227.8 2160.8 2133 2113.8
[1]

Jiulong Liu, Nanguang Chen, Hui Ji. Learnable Douglas-Rachford iteration and its applications in DOT imaging. Inverse Problems & Imaging, 2020, 14 (4) : 683-700. doi: 10.3934/ipi.2020031

[2]

Tahereh Salimi Siahkolaei, Davod Khojasteh Salkuyeh. A preconditioned SSOR iteration method for solving complex symmetric system of linear equations. Numerical Algebra, Control & Optimization, 2019, 9 (4) : 483-492. doi: 10.3934/naco.2019033

[3]

Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855

[4]

Raphael Kruse, Yue Wu. A randomized Milstein method for stochastic differential equations with non-differentiable drift coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3475-3502. doi: 10.3934/dcdsb.2018253

[5]

Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1

[6]

Olivier Bokanowski, Maurizio Falcone, Roberto Ferretti, Lars Grüne, Dante Kalise, Hasnaa Zidani. Value iteration convergence of $\epsilon$-monotone schemes for stationary Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4041-4070. doi: 10.3934/dcds.2015.35.4041

[7]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020013

[8]

Purnima Pandit. Fuzzy system of linear equations. Conference Publications, 2013, 2013 (special) : 619-627. doi: 10.3934/proc.2013.2013.619

[9]

Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507

[10]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[11]

Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052

[12]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020018

[13]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020185

[14]

Liu Liu. Uniform spectral convergence of the stochastic Galerkin method for the linear semiconductor Boltzmann equation with random inputs and diffusive scaling. Kinetic & Related Models, 2018, 11 (5) : 1139-1156. doi: 10.3934/krm.2018044

[15]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020203

[16]

Michela Eleuteri, Pavel Krejčí. An asymptotic convergence result for a system of partial differential equations with hysteresis. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1131-1143. doi: 10.3934/cpaa.2007.6.1131

[17]

Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008

[18]

Z. K. Eshkuvatov, M. Kammuji, Bachok M. Taib, N. M. A. Nik Long. Effective approximation method for solving linear Fredholm-Volterra integral equations. Numerical Algebra, Control & Optimization, 2017, 7 (1) : 77-88. doi: 10.3934/naco.2017004

[19]

B. S. Lee, Arif Rafiq. Strong convergence of an implicit iteration process for a finite family of Lipschitz $\phi -$uniformly pseudocontractive mappings in Banach spaces. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 287-293. doi: 10.3934/naco.2014.4.287

[20]

Byung-Soo Lee. Strong convergence theorems with three-step iteration in star-shaped metric spaces. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 371-379. doi: 10.3934/naco.2011.1.371

 Impact Factor: 

Metrics

  • PDF downloads (34)
  • HTML views (37)
  • Cited by (0)

Other articles
by authors

[Back to Top]