American Institute of Mathematical Sciences

Advanced
January  2022, 27(1): 555-568. 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  January 2022 Early access  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, 2022, 27 (1) : 555-568. 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]

Gang Li, Minghua Li, Yaohua Hu. Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021127
[2]

Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547
[3]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
[4]

Zeng-Zhen Tan, Rong Hu, Ming Zhu, Ya-Ping Fang. A dynamical system method for solving the split convex feasibility problem. Journal of Industrial & Management Optimization, 2021, 17 (6) : 2989-3011. doi: 10.3934/jimo.2020104
[5]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859
[6]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[7]

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
[8]

Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925
[9]

H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175
[10]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247
[11]

Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016
[12]

Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047
[13]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078
[14]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057
[15]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
[16]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917
[17]

Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069
[18]

Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341
[19]

Xin Yang, Nan Wang, Lingling Xu. A parallel Gauss-Seidel method for convex problems with separable structure. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 557-570. doi: 10.3934/naco.2020051
[20]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023

2020 Impact Factor: 1.327

Tools

Metrics

  • PDF downloads (199)
  • HTML views (381)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy