American Institute of Mathematical Sciences

Advanced
doi: 10.3934/dcdsb.2021054

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

Received  June 2020 Revised  November 2020 Published  February 2021

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: Convex feasibility problems, method of alternating projections, Kaczmarz method, algebraic reconstruction technique, acceleration by learning.
Mathematics Subject Classification: Primary: 65K05, 52B55, 37B20; Secondary: 90C59.
Citation: Janosch Rieger. A learning-enhanced projection method for solving convex feasibility problems. Discrete & Continuous Dynamical Systems - B, doi: 10.3934/dcdsb.2021054
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[8]

Y. Censor, Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23 (1981), 444-466.  doi: 10.1137/1023097.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[8]

Y. Censor, Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23 (1981), 444-466.  doi: 10.1137/1023097.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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 $
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[2]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[4]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[5]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[6]

Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021012
[7]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080
[8]

Xue-Ping Luo, Yi-Bin Xiao, Wei Li. Strict feasibility of variational inclusion problems in reflexive Banach spaces. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2495-2502. doi: 10.3934/jimo.2019065
[9]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[10]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196
[11]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[12]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[13]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044
[14]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[15]

Mikhail Dokuchaev, Guanglu Zhou, Song Wang. A modification of Galerkin's method for option pricing. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021077
[16]

Jiahui Chen, Rundong Zhao, Yiying Tong, Guo-Wei Wei. Evolutionary de Rham-Hodge method. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3785-3821. doi: 10.3934/dcdsb.2020257
[17]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[18]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[19]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[20]

Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042

2019 Impact Factor: 1.27

Tools

Metrics

  • PDF downloads (15)
  • HTML views (79)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences