A learning-enhanced projection method for solving convex feasibility problems

Janosch Rieger

doi:10.3934/dcdsb.2021054

Article Contents

2022, Volume 27, Issue 1: 555-568. Doi: 10.3934/dcdsb.2021054

This issue Previous Article Dynamics of Timoshenko system with time-varying weight and time-varying delay Next Article Stabilization by intermittent control for hybrid stochastic differential delay equations

A learning-enhanced projection method for solving convex feasibility problems

Janosch Rieger^,

School of Mathematics, Monash University, 9 Rainforest Walk, Victoria 3800 Australia

^* Corresponding author: Janosch Rieger
^* Corresponding author: Janosch Rieger

Received: May 31, 2020

Revised: October 31, 2020

Early access: February 2021

Published: January 2022

Abstract Full Text(HTML) Figure(5) Related Papers Cited by

Abstract

We propose a generalization of the method of cyclic projections, which uses the lengths of projection steps carried out in the past to learn about the geometry of the problem and decides on this basis which projections to carry out in the future. We prove the convergence of this algorithm and illustrate its behavior in a first numerical study.

Keywords:

Mathematics Subject Classification: Primary: 65K05, 52B55, 37B20; Secondary: 90C59.

Citation:

Full Text(HTML)

Figure 1. Methods MCP, MRP and PAM applied to toy problem. Top row: Iterates red, subspaces blue. Bottom row: Frequencies (yellow = high, blue = low) of transitions from set $ C_m $ to set $ C_n $

Download: Full-size image PowerPoint slide

Figure 2. Trajectories and frequencies of PAM as in Example 4(ⅰ)

Download: Full-size image PowerPoint slide

Figure 3. Trajectories and frequencies of PAM as in Example 4(ⅱ)

Download: Full-size image PowerPoint slide

Figure 4. Trajectories and frequencies of PAM as in Example 5

Download: Full-size image PowerPoint slide

Figure 5. Error plots of methods applied to toy model with varying parameters. Solid black line MCP, dashed black line MRP, solid red line PAM $ \omega = N/4 $, dashed red line PAM $ \omega = N/2 $, dash-dotted red line PAM $ \omega = N $. More details given in Example 6

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	F. Arroyo, E. Arroyo, X. Li and J. Zhu, The convergence of the block cyclic projection with an overrelaxation parameter for compressed sensing based tomography, J. Comput. Appl. Math., 280 (2015), 59-67. doi: 10.1016/j.cam.2014.11.036.
[2]	Z.-Z. Bai and W.-T. Wu, On greedy randomized {K}aczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. doi: 10.1137/17M1137747.
[3]	H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Rev., 38 (1996), 367-426. doi: 10.1137/S0036144593251710.
[4]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2011. doi: 10.1007/978-1-4419-9467-7.
[5]	H. H. Bauschke, F. Deutsch, H. Hundal and S.-H. Park, Accelerating the convergence of the method of alternating projections, Trans. Amer. Math. Soc., 355 (2003), 3433-3461. doi: 10.1090/S0002-9947-03-03136-2.
[6]	J. M. Borwein, G. Li and L. Yao, Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets, SIAM J. Optim., 24 (2014), 498-527. doi: 10.1137/130919052.
[7]	L. M. Brègman, Finding the common point of convex sets by the method of successive projection, Dokl. Akad. Nauk SSSR, 162 (1965), 487-490.
[8]	Y. Censor, Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23 (1981), 444-466. doi: 10.1137/1023097.
[9]	F. Deutsch, Best Approximation in Inner Product Spaces, Volume 7 of CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC., Springer-Verlag, New York, 2001. doi: 10.1007/978-1-4684-9298-9.
[10]	T. Elfving, P. C. Hansen and T. Nikazad, Convergence analysis for column-action methods in image reconstruction, Numer. Algorithms, 74 (2017), 905-924. doi: 10.1007/s11075-016-0176-x.
[11]	L. Elsner, I. Koltracht and M. Neumann, Convergence of sequential and asynchronous nonlinear paracontractions, Numer. Math., 62 (1992), 305-319. doi: 10.1007/BF01396232.
[12]	C. Franchetti and W. Light, On the von {N}eumann alternating algorithm in {H}ilbert space, J. Math. Anal. Appl., 114 (1986), 305-314. doi: 10.1016/0022-247X(86)90085-5.
[13]	W. B. Gearhart and M. Koshy, Acceleration schemes for the method of alternating projections, J. Comput. Appl. Math., 26 (1989), 235-249. doi: 10.1016/0377-0427(89)90296-3.
[14]	G. S. M. Jansen, M. Keunecke, M. Düvel, C. Möller, D. Schmitt, W. Bennecke, F. J. S. Kappert, D. Steil, D. R. Luke, S. Steil and S. Mathias, Efficient orbital imaging based on ultrafast momentum microscopy and sparsity-driven phase retrieval, New Journal of Physics, 22 (2020), 063012. doi: 10.1088/1367-2630/ab8aae.
[15]	M. Jiang and G. Wang, Convergence studies on iterative algorithms for image reconstruction, IEEE Trans. Med. Imaging, 22 (2003), 569-579. doi: 10.1109/TMI.2003.812253.
[16]	S. Kaczmarz, 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.
[17]	T. Strohmer and R. Vershynin, A randomized {K}aczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262-278. doi: 10.1007/s00041-008-9030-4.
[18]	M. K. Tam, Gearhart-Koshy acceleration for affine subspaces, Operations Research Letters, 49 (2021), 157-163. doi: 10.1016/j.orl.2020.12.007.
[19]	N. H. Thao, D. R. Luke, O. Soloviev and M. Verhaegen, Phase retrieval with sparse phase constraint, SIAM J. Mathematics of Data Science, 2 (2020), 246-263. doi: 10.1137/19M1266800.