Skip to main content
SpringerLink
Log in

Convergence and perturbation resilience of dynamic string-averaging projection methods

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We consider the convex feasibility problem (CFP) in Hilbert space and concentrate on the study of string-averaging projection (SAP) methods for the CFP, analyzing their convergence and their perturbation resilience. In the past, SAP methods were formulated with a single predetermined set of strings and a single predetermined set of weights. Here we extend the scope of the family of SAP methods to allow iteration-index-dependent variable strings and weights and term such methods dynamic string-averaging projection (DSAP) methods. The bounded perturbation resilience of DSAP methods is relevant and important for their possible use in the framework of the recently developed superiorization heuristic methodology for constrained minimization problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aharoni, R., Censor, Y.: Block-iterative projection methods for parallel computation of solutions to convex feasibility problems. Linear Algebra Appl. 120, 165–175 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)

    Book  MATH  Google Scholar 

  4. Bauschke, H.H., Matoušková, E., Reich, S.: Projection and proximal point methods: convergence results and counterexamples. Nonlinear Anal., Theory Methods Appl. 56, 715–738 (2004)

    Article  MATH  Google Scholar 

  5. Butnariu, D., Davidi, R., Herman, G.T., Kazantsev, I.G.: Stable convergence behavior under summable perturbations of a class of projection methods for convex feasibility and optimization problems. IEEE J. Sel. Top. Signal Process. 1, 540–547 (2007)

    Article  Google Scholar 

  6. Butnariu, D., Reich, S., Zaslavski, A.J.: Stable convergence theorems for infinite products and powers of nonexpansive mappings. Numer. Funct. Anal. Optim. 29, 304–323 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Byrne, C.L.: Applied Iterative Methods. AK Peters, Wellsely (2008)

    MATH  Google Scholar 

  8. Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Lecture Notes in Mathematics. Springer, Berlin (2012, to appear)

    MATH  Google Scholar 

  9. Censor, Y., Chen, W., Combettes, P.L., Davidi, R., Herman, G.T.: On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints. Comput. Optim. Appl. 51, 1065–1088 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  10. Censor, Y., Davidi, R., Herman, G.T.: Perturbation resilience and superiorization of iterative algorithms. Inverse Probl. 26, 065008 (2010) (12 pp.)

    Article  MathSciNet  Google Scholar 

  11. Censor, Y., Elfving, T., Herman, G.T.: Averaging strings of sequential iterations for convex feasibility problems. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 101–114. Elsevier Science, Amsterdam (2001)

    Chapter  Google Scholar 

  12. Censor, Y., Segal, A.: On the string averaging method for sparse common fixed point problems. Int. Trans. Oper. Res. 16, 481–494 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  13. Censor, Y., Segal, A.: On string-averaging for sparse problems and on the split common fixed point problem. Contemp. Math. 513, 125–142 (2010)

    Article  MathSciNet  Google Scholar 

  14. Censor, Y., Tom, E.: Convergence of string-averaging projection schemes for inconsistent convex feasibility problems. Optim. Methods Softw. 18, 543–554 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  15. Censor, Y., Zenios, S.A.: Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, New York (1997)

    MATH  Google Scholar 

  16. Chinneck, J.W.: Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods. Springer, New York (2007)

    Google Scholar 

  17. Combettes, P.L.: Quasi-Fejérian analysis of some optimization algorithms. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 115–152. Elsevier, New York (2001)

    Chapter  Google Scholar 

  18. Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53, 475–504 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  19. Crombez, G.: Finding common fixed points of strict paracontractions by averaging strings of sequential iterations. J. Nonlinear Convex Anal. 3, 345–351 (2002)

    MathSciNet  MATH  Google Scholar 

  20. Davidi, R., Herman, G.T., Censor, Y.: Perturbation-resilient block-iterative projection methods with application to image reconstruction from projections. Int. Trans. Oper. Res. 16, 505–524 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Escalante, R., Raydan, M.: Alternating Projection Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2011)

    Book  MATH  Google Scholar 

  22. Galántai, A.: Projectors and Projection Methods. Kluwer Academic, Dordrecht (2004)

    MATH  Google Scholar 

  23. Herman, G.T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections, 2nd edn. Springer, London (2009)

    Google Scholar 

  24. Herman, G.T., Davidi, R.: Image reconstruction from a small number of projections. Inverse Probl. 24, 045011 (2008) (17 pp.)

    Article  MathSciNet  Google Scholar 

  25. Herman, G.T., Garduño, E., Davidi, R., Censor, Y.: Superiorization: an optimization heuristic with application to tomography. Technical Report (12 January 2012)

  26. Nikazad, T., Davidi, R., Herman, G.T.: Accelerated perturbation-resilient block-iterative projection methods with application to image reconstruction. Inverse Probl. 28, 035005 (2012) (19 pp.)

    Article  MathSciNet  Google Scholar 

  27. Penfold, S.N., Schulte, R.W., Censor, Y., Bashkirov, V., McAllister, S., Schubert, K.E., Rosenfeld, A.B.: Block-iterative and string-averaging projection algorithms in proton computed tomography image reconstruction. In: Censor, Y., Jiang, M., Wang, G. (eds.) Biomedical Mathematics: Promising Directions in Imaging, Therapy Planning and Inverse Problems, pp. 347–367. Medical Physics Publishing, Madison (2010)

    Google Scholar 

  28. Penfold, S.N., Schulte, R.W., Censor, Y., Rosenfeld, A.B.: Total variation superiorization schemes in proton computed tomography image reconstruction. Med. Phys. 37, 5887–5895 (2010)

    Article  Google Scholar 

  29. Rhee, H.: An application of the string averaging method to one-sided best simultaneous approximation. J. Korea Soc. Math. Educ. Ser. B Pure Appl. Math. 10, 49–56 (2003)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We gratefully acknowledge enlightening discussions with Gabor Herman on the topics discussed in this paper. The work of the first author was supported by the United States-Israel Binational Science Foundation (BSF) Grant number 200912 and US Department of Army Award number W81XWH-10-1-0170.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, Mt. Carmel, Haifa, 31905, Israel

    Yair Censor

  2. Department of Mathematics, The Technion—Israel Institute of Technology, Technion City, Haifa, 32000, Israel

    Alexander J. Zaslavski

Authors
  1. Yair Censor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexander J. Zaslavski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yair Censor.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Censor, Y., Zaslavski, A.J. Convergence and perturbation resilience of dynamic string-averaging projection methods. Comput Optim Appl 54, 65–76 (2013). https://doi.org/10.1007/s10589-012-9491-x

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-012-9491-x

Keywords

Search

Navigation