×

The block-wise circumcentered-reflection method. (English) Zbl 1445.90080

Summary: The elementary Euclidean concept of a circumcenter has recently been employed to improve two aspects of the classical Douglas-Rachford method for projecting onto the intersection of affine subspaces. The so-called circumcentered-reflection method is able to both accelerate the average reflection scheme by the Douglas-Rachford method and cope with the intersection of more than two affine subspaces. We now introduce the technique of circumcentering in blocks, which, more than just an option over the basic algorithm of circumcenters, turns out to be an elegant manner of generalizing the method of alternating projections. Linear convergence for this novel block-wise circumcenter framework is derived and illustrated numerically. Furthermore, we prove that the original circumcentered-reflection method essentially finds the best approximation solution in one single step if the given affine subspaces are hyperplanes.

MSC:

90C25 Convex programming
49M27 Decomposition methods
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aragón Artacho, FJ; Borwein, JM; Tam, MK, Recent results on Douglas-Rachford methods for combinatorial optimization problems, J. Optim. Theory Appl., 163, 1, 1-30 (2013) · Zbl 1305.90341
[2] Aragón Artacho, F.J., Campoy, R., Tam, M.K.: The Douglas-Rachford algorithm for convex and nonconvex feasibility problems. arXiv:1904.09148 (2019) · Zbl 1435.65090
[3] Bauschke, HH; Bello-Cruz, JY; Nghia, TTA; Phan, HM; Wang, X., The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle, J. Approx. Theory, 185, 63-79 (2014) · Zbl 1307.49030
[4] Bauschke, HH; Bello-Cruz, JY; Nghia, TTA; Phan, HM; Wang, X., Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces, Numer. Algorithms, 73, 1, 33-76 (2016) · Zbl 1351.65022
[5] Bauschke, HH; Borwein, JM, On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Anal., 1, 2, 185-212 (1993) · Zbl 0801.47042
[6] Bauschke, HH; Borwein, JM, On projection algorithms for solving convex feasibility problems, SIAM Rev., 38, 3, 367-426 (2006) · Zbl 0865.47039
[7] Bauschke, HH; Deutsch, FR; Hundal, H.; Park, SH, Accelerating the convergence of the method of alternating projections, Trans. Am. Math. Soc., 355, 9, 3433-3461 (2003) · Zbl 1033.41019
[8] Bauschke, HH; Luke, DR; Phan, HM; Wang, X., Restricted normal cones and the method of alternating projections: theory, Set-Valued Var. Anal., 21, 3, 431-473 (2013) · Zbl 1272.49027
[9] Bauschke, HH; Moursi, WM, The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces, SIAM J. Optim., 26, 2, 968-985 (2016) · Zbl 1341.47064
[10] Bauschke, HH; Ouyang, H.; Wang, X., On circumcenters of finite sets in Hilbert spaces, Linear Nonlinear Anal., 4, 2, 271-295 (2018) · Zbl 1456.51008
[11] Bauschke, H.H., Ouyang, H., Wang, X.: Circumcentered methods induced by isometries. arXiv:1908.11576 (2019)
[12] Bauschke, H.H., Ouyang, H., Wang, X.: On circumcenter mappings induced by nonexpansive operators. Pure Appl. Funct. Anal. (in press) · Zbl 1491.47042
[13] Behling, R.; Bello-Cruz, JY; Santos, LR, Circumcentering the Douglas-Rachford method, Numer. Algorithms, 78, 3, 759-776 (2018) · Zbl 1395.49023
[14] Behling, R.; Bello-Cruz, JY; Santos, LR, On the linear convergence of the circumcentered-reflection method, Oper. Res. Lett., 46, 2, 159-162 (2018) · Zbl 1525.90328
[15] Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, VB, Julia: a fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98 (2017) · Zbl 1356.68030
[16] Boisvert, RF; Pozo, R.; Remington, K.; Barrett, RF; Dongarra, JJ; Boisvert, RF, Matrix market: a web resource for test matrix collections, Quality of Numerical Software, 125-137 (1997), Boston: Springer, Boston
[17] Borwein, JM; Tam, MK, A cyclic Douglas-Rachford iteration scheme, J. Optim. Theory Appl., 160, 1, 1-29 (2014) · Zbl 1305.90407
[18] Borwein, JM; Tam, MK, The cyclic Douglas-Rachford method for inconsistent feasibility problems, J. Nonlinear Convex Anal., 16, 4, 573-584 (2015) · Zbl 1315.47061
[19] Demanet, L.; Zhang, X., Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit, Math. Comput., 85, 297, 209-238 (2016) · Zbl 1329.49050
[20] Deutsch, FR; Singh, SP, The angle between subspaces of a Hilbert space, Approximation Theory, Wavelets and Applications, 107-130 (1995), Dordrecht: Springer, Dordrecht · Zbl 0848.46010
[21] Deutsch, FR, Best Approximation in Inner Product Spaces. CMS Books in Mathematics (2001), New York: Springer, New York · Zbl 0980.41025
[22] Hansen, PC; Jørgensen, JS, AIR tools II: algebraic iterative reconstruction methods, improved implementation, Numer. Algorithms, 79, 1, 107-137 (2017) · Zbl 1397.65007
[23] Herman, GT, Fundamentals of Computerized Tomography, 2 edn. Advances in Pattern Recognition. (2009), Dordrecht: Springer, Dordrecht · Zbl 1280.92002
[24] Hesse, R.; Luke, DR, Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim., 23, 4, 2397-2419 (2013) · Zbl 1288.65094
[25] Hesse, R.; Luke, DR; Neumann, P., Alternating projections and Douglas-Rachford for sparse affine feasibility, IEEE Trans. Signal Process., 62, 18, 4868-4881 (2014) · Zbl 1394.94227
[26] Lindstrom, S.B., Sims, B.: Survey: sixty years of Douglas-Rachford. arXiv:1809.07181 (2018)
[27] Ouyang, H.: Circumcenter operators in Hilbert spaces. Master’s Thesis, University of British Columbia, Okanagan (2018)
[28] Shepp, LA; Logan, BF, The fourier reconstruction of a head section, IEEE Trans. Nucl. Sci., 21, 3, 21-43 (1974)
[29] Strohmer, T.; Vershynin, R., A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 2, 262-278 (2008) · Zbl 1169.68052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.