Convergence of a randomized Douglas-Rachford method for linear system

Leyu Hu; Xingju Cai

doi:10.3934/naco.2020045

Article Contents

2020, Volume 10, Issue 4: 463-474. Doi: 10.3934/naco.2020045

This issue Previous Article An improved algorithm for generalized least squares estimation Next Article A trust region algorithm for computing extreme eigenvalues of tensors

Convergence of a randomized Douglas-Rachford method for linear system

Leyu Hu and
Xingju Cai

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

Received: February 29, 2020

Revised: August 31, 2020

Published: September 2020

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

Abstract Full Text(HTML) Figure(1) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 65F10, 65F20, 65K05, 90C25, 90C15, 15A06.

Citation:

Full Text(HTML)

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 $

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[6]	H. H. Bauschke, J. 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.
[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.
[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.
[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.
[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.
[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.
[12]	R. L. Dykstra, An algorithm for restricted least squares regression, Journal of the American Statistical Association, 78 (1983), 837-842.
[13]	T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numerische Mathematik, 35 (1980), 1-12. doi: 10.1007/BF01396365.
[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.
[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.
[16]	D. Needell, R. 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.
[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.
[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.
[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.