
-
Previous Article
Singular support of the global attractor for a damped BBM equation
- DCDS-B Home
- This Issue
-
Next Article
Local well-posedness for the density-dependent incompressible magneto-micropolar system with vacuum
A learning-enhanced projection method for solving convex feasibility problems
School of Mathematics, Monash University, 9 Rainforest Walk, Victoria 3800 Australia |
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.
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. 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. |
[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. |
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. |
[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. 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. |
[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. |





[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
Other articles
by authors
[Back to Top]