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.
Citation: |
[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.![]() ![]() ![]() |
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
Trajectories and frequencies of PAM as in Example 4(ⅰ)
Trajectories and frequencies of PAM as in Example 4(ⅱ)
Trajectories and frequencies of PAM as in Example 5
Error plots of methods applied to toy model with varying parameters. Solid black line MCP, dashed black line MRP, solid red line PAM