Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A block coordinate variable metric linesearch based proximal gradient method

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

Abstract

In this paper we propose an alternating block version of a variable metric linesearch proximal gradient method. This algorithm addresses problems where the objective function is the sum of a smooth term, whose variables may be coupled, plus a separable part given by the sum of two or more convex, possibly nonsmooth functions, each depending on a single block of variables. Our approach is characterized by the possibility of performing several proximal gradient steps for updating every block of variables and by the Armijo backtracking linesearch for adaptively computing the steplength parameter. Under the assumption that the objective function satisfies the Kurdyka-Łojasiewicz property at each point of its domain and the gradient of the smooth part is locally Lipschitz continuous, we prove the convergence of the iterates sequence generated by the method. Numerical experience on an image blind deconvolution problem show the improvements obtained by adopting a variable number of inner block iterations combined with a variable metric in the computation of the proximal operator.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Abboud, F., Chouzenoux, E., Pesquet, J.C., Chenot, J.H., Laborelli, L.: Dual block coordinate forward–backward algorithm with application to deconvolution and deinterlacing of video sequences. J. Math. Imaging Vis. 59(3), 415–431 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  2. Almeida, M.S.C., Almeida, L.B.: Blind and semi-blind deblurring of natural images. IEEE Trans. Image Process. 19(1), 36–52 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  3. Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116(1–2), 5–16 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Math. Program. 137(1–2), 91–129 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Ayers, G.R., Dainty, J.C.: Iterative blind deconvolution method and its applications. Opt. Lett. 13(7), 547–549 (1988)

    Article  Google Scholar 

  7. Bauschke, H.H., Bolte, J., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res. 4(1), 330–348 (2016)

    MathSciNet  MATH  Google Scholar 

  8. Bertero, M., Bindi, D., Boccacci, P., Cattaneo, M., Eva, C., Lanza, V.: A novel blind-deconvolution method with an application to seismology. Inverse Probl. 14(4), 815–833 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bertero, M., Boccacci, P., Desiderà, G., Vicidomini, G.: Image deblurring with Poisson data: from cells to galaxies. Inverse Probl. 25(12), 123006 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bertero, M., Lantéri, H., Zanni, L.: Iterative image reconstruction: a point of view. In: Censor, Y., Jiang, M., Louis, A.K. (eds.) Mathematical Methods in Biomedical Imaging and Intensity-Modulated Radiation Therapy (IMRT), pp. 37–63. Birkhauser, Pisa (2008)

    Google Scholar 

  11. Bertsekas, D.: Nonlinear Programming. Athena Scientific, Belmont (1999)

    MATH  Google Scholar 

  12. Bolte, J., Combettes, P.L., Pesquet, J.C.: Alternating proximal algorithm for blind image recovery. In: Proceedings of the 17th International Conference on Image Processing, pp. 1673–1676 (2010)

  13. Bolte, J., Daniilidis, A., Ley, O., Mazet, L.: Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Am. Math. Soc. 362(6), 3319–3363 (2010)

    Article  MATH  Google Scholar 

  14. Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1–2), 459–494 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Bonettini, S.: Inexact block coordinate descent methods with application to the nonnegative matrix factorization. IMA J. Numer. Anal. 31(4), 1431–1452 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  16. Bonettini, S., Cornelio, A., Prato, M.: A new semiblind deconvolution approach for Fourier-based image restoration: an application in astronomy. SIAM J. Imaging Sci. 6(3), 1736–1757 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  17. Bonettini, S., Loris, I., Porta, F., Prato, M.: Variable metric inexact line-search based methods for nonsmooth optimization. SIAM J. Optim. 26(2), 891–921 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  18. Bonettini, S., Loris, I., Porta, F., Prato, M., Rebegoldi, S.: On the convergence of a linesearch based proximal-gradient method for nonconvex optimization. Inverse Probl. 33(5), 055005 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  19. Bonettini, S., Prato, M.: New convergence results for the scaled gradient projection method. Inverse Probl. 31(9), 095008 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  20. Bonettini, S., Prato, M., Rebegoldi, S.: A cyclic block coordinate descent method with generalized gradient projections. Appl. Math. Comput. 286, 288–300 (2016)

    MathSciNet  Google Scholar 

  21. Bonettini, S., Zanella, R., Zanni, L.: A scaled gradient projection method for constrained image deblurring. Inverse Probl. 25(1), 015002 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  22. Cassioli, A., Di Lorenzo, D., Sciandrone, M.: On the convergence of inexact block coordinate descent methods for constrained optimization. Eur. J. Oper. Res. 231(2), 274–281 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  23. Chambolle, A., Dossal, C.: On the convergence of the iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”. J. Optim. Theory Appl. 166(3), 968–982 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  24. Chouzenoux, E., Pesquet, J.C.: A stochastic majorize-minimize subspace algorithm for online penalized least squares estimation. IEEE Trans. Signal Process. 65(18), 4770–4783 (2017)

    Article  MathSciNet  Google Scholar 

  25. Chouzenoux, E., Pesquet, J.C., Repetti, A.: Variable metric forward–backward algorithm for minimizing the sum of a differentiable function and a convex function. J. Optim. Theory Appl. 162(1), 107–132 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  26. Chouzenoux, E., Pesquet, J.C., Repetti, A.: A block coordinate variable metric forward–backward algorithm. J. Glob. Optim. 66(3), 457–485 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Combettes, P.L., Pesquet, J.C.: Proximal splitting methods in signal processing. In: Bauschke, H.H., Burachik, R.S., Combettes, P.L., Elser, V., Luke, D.R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Springer Optimization and Its Applications, pp. 185–212. Springer, New York (2011)

    Chapter  Google Scholar 

  28. Cornelio, A., Porta, F., Prato, M.: A convergent least-squares regularized blind deconvolution approach. Appl. Math. Comput. 259, 173–186 (2015)

    MathSciNet  MATH  Google Scholar 

  29. Fessler, J.A., Erdogan, H.: A paraboloidal surrogates algorithm for convergent penalized–likelihood emission image reconstruction. In: 1998 IEEE Nuclear Science Symposium Conference Record, pp. 1132–1135 (1998)

  30. Frankel, P., Garrigos, G., Peypouquet, J.: Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. J. Opt. Theory Appl. 165(3), 874–900 (2015)

    Article  MATH  Google Scholar 

  31. Grippo, L., Sciandrone, M.: Globally convergent block-coordinate techniques for unconstrained optimization. Optim. Method Softw. 10(4), 587–637 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  32. Grippo, L., Sciandrone, M.: On the convergence of the block nonlinear Gauss–Seidel method under convex constraints. Oper. Res. Lett. 26(3), 127–136 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  33. Harmany, Z., Marcia, R., Willett, R.: This is SPIRAL-TAP: sparse Poisson intensity reconstruction algorithms—theory and practice. IEEE Trans. Image Process. 21(3), 1084–1096 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  34. Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, New York (1993)

    MATH  Google Scholar 

  35. Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier 48(3), 769–783 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  36. Lantéri, H., Roche, M., Cuevas, O., Aime, C.: A general method to devise maximum likelihood signal restoration multiplicative algorithms with non-negativity constraints. Signal Process. 81(5), 945–974 (2001)

    Article  MATH  Google Scholar 

  37. Lee, D., Seung, H.: Algorithms for non-negative matrix factorization. In: NIPS, pp. 556–562. MIT Press (2000)

  38. Lin, C.J.: Projected gradient methods for nonnegative matrix factorization. Neural Comput. 19(10), 2756–2779 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  39. Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels. In: Les Équations aux Dérivées Partielles, pp. 87–89. Éditions du Centre National de la Recherche Scientifique, Paris (1963)

  40. Lucy, L.B.: An iterative technique for the rectification of observed distributions. Astronom. J. 79(6), 745–754 (1974)

    Article  Google Scholar 

  41. Noll, D.: Convergence of non-smooth descent methods using the Kurdyka-Łojasiewicz inequality. J. Opt. Theory Appl. 160(2), 553–572 (2014)

    Article  MATH  Google Scholar 

  42. Ochs, P.: Unifying abstract inexact convergence theorems for descent methods and block coordinate variable metric iPiano (2016). arXiv:1602.07283

  43. Ochs, P., Chen, Y., Brox, T., Pock, T.: iPiano: inertial proximal algorithm for non-convex optimization. SIAM J. Imaging Sci. 7(2), 1388–1419 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  44. Porta, F., Loris, I.: On some steplength approaches for proximal algorithms. Appl. Math. Comput. 253, 345–362 (2015)

    MathSciNet  MATH  Google Scholar 

  45. Prato, M., Camera, A.L., Bonettini, S., Bertero, M.: A convergent blind deconvolution method for post-adaptive-optics astronomical imaging. Inverse Probl. 29(6), 065017 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  46. Prato, M., Cavicchioli, R., Zanni, L., Boccacci, P., Bertero, M.: Efficient deconvolution methods for astronomical imaging: algorithms and IDL-GPU codes. Astron. Astrophys. 539, A133 (2012)

    Article  Google Scholar 

  47. Prato, M., La Camera, A., Bonettini, S., Rebegoldi, S., Bertero, M., Boccacci, P.: A blind deconvolution method for ground based telescopes and Fizeau interferometers. New Astron. 40, 1–13 (2015)

    Article  Google Scholar 

  48. Razaviyayn, M., Hong, M., Luo, Z.Q.: A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM J. Optim. 23(2), 1126–1153 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  49. Rockafellar, R.T., Wets, R.J.B., Wets, M.: Variational Analysis. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  50. Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. J. Phys. D. 60(1–4), 259–268 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  51. Salzo, S.: The variable metric forward–backward splitting algorithm under mild differentiability assumptions. SIAM J. Optim. 27(4), 2153–2181 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  52. Salzo, S., Villa, S.: Inexact and accelerated proximal point algorithms. J. Convex Anal. 19(4), 1167–1192 (2012)

    MathSciNet  MATH  Google Scholar 

  53. Shen, X., Diamond, S., Udell, M., Gu, Y., Boyd, S.: Disciplined multi-convex programming (2016). arXiv:1609.03285

  54. Staglianò, A., Boccacci, P., Bertero, M.: Analysis of an approximate model for Poisson data reconstruction and a related discrepancy principle. Inverse Probl. 27(12), 125003 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  55. Tikhonov, N.A., Arsenin, V.Y.: Solution of Ill Posed Problems. Wiley, New York (1977)

    MATH  Google Scholar 

  56. Tseng, P., Yun, S.: A coordinate gradient descent method for nonsmooth separable minimization. Math. Program. 117(1–2), 387–423 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  57. Villa, S., Salzo, S., Baldassarre, L., Verri, A.: Accelerated and inexact forward–backward algorithms. SIAM J. Optim. 23(3), 1607–1633 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  58. Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3), 1758–1789 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  59. Zalinescu, A.: Convex Analysis in General Vector Spaces. World Scientific Publishing Co., Inc., River Edge (2002)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Università di Modena e Reggio Emilia, Via Campi 213/b, 41125, Modena, Italy

    S. Bonettini & M. Prato

  2. Dipartimento di Matematica e Informatica, Università di Ferrara, Via Machiavelli 35, 44121, Ferrara, Italy

    S. Rebegoldi

Authors
  1. S. Bonettini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Prato
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. Rebegoldi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Bonettini.

Additional information

This work is supported by MIUR under the Project FIRB Futuro in Ricerca 2012, Contract RBFR12M3AC. The Italian GNCS-INdAM is also acknowledged.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bonettini, S., Prato, M. & Rebegoldi, S. A block coordinate variable metric linesearch based proximal gradient method. Comput Optim Appl 71, 5–52 (2018). https://doi.org/10.1007/s10589-018-0011-5

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-018-0011-5

Keywords

Search

Navigation