A Preconditioned Difference of Convex Algorithm for Truncated Quadratic Regularization with Application to Imaging
Abstract
We consider the minimization problem with the truncated quadratic regularization, which is a nonsmooth and nonconvex problem. We cooperated the classical preconditioned iterations for linear equations into the nonlinear difference of convex functions algorithms with extrapolation. Especially, our preconditioned framework can deal with the large linear system efficiently which is usually expensive for computations. Global convergence is guaranteed and local linear convergence rate is given based on the analysis of the Kurdyka–Łojasiewicz exponent of the minimization functional. The proposed algorithm with preconditioners turns out to be very efficient for image restoration and is also appealing for image segmentation.
References
[1]
Attouch H and Bolte J On the convergence of the proximal algorithm for nonsmooth functions involving analytic features Math. Progr. Ser. B 2009 116 5-16
[2]
Attouch H, Bolte J, Redont P, and Soubeyran A Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–Łojasiewicz inequality Math. Oper. Res. 2010 35 2 438-457
[3]
Attouch H, Bolte J, and Svaiter BF Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss–Seidel methods Math. Program. 2013 137 91-129
[4]
Allain M, Idier J, and Goussard Y On global and local convergence of half-quadratic algorithms IEEE Trans. Image Process. 2006 15 1130-1142
[5]
Aubert G and Vese L Variational methods in image restoration SIAM J. Numer. Anal. 1997 34 5 1948-1979
[6]
Bredies K and Sun H Preconditioned Douglas–Rachford splitting methods for convex-concave saddle-point problems SIAM J. Numer. Anal. 2015 53 1 421-444
[7]
Bredies K and Sun H Preconditioned Douglas–Rachford algorithms for TV- and TGV-regularized variational imaging problems J. Math. Imaging Vis. 2015 52 3 317-344
[8]
Bredies K and Sun H A proximal point analysis of the preconditioned alternating direction method of multipliers J. Optim. Theory Appl. 2017 173 3 878-907
[9]
Bolte J, Sabach S, and Teboulle M Proximal alternating linearized minimization for nonconvex and nonsmooth problems Math. Progr. Ser. A 2014 146 459-494
[10]
Boykov Y, Veksler O, and Zabih R Fast approximate energy minimization via graph cuts IEEE Trans. Pattern Anal. Mach. Intell. 2001 23 1222-1239
[11]
Blake A and Zisserman A Visual Reconstruction 1987 London The MIT Press
[12]
Chambolle A and Pock T A first-order primal-dual algorithm for convex problems with applications to imaging J. Math. Imaging Vis. 2011 40 1 120-145
[13]
Chan R, Lanza A, Morigi S, and Sgallari F Convex non-convex image segmentation Numer. Math. 2018 138 635-680
[14]
Chambolle A Image segmentation by variational methods: mumford and shah functional and the discrete approximations SIAM J. Appl. Math. 1995 55 3 827-863
[15]
Charbonnier, P., Blanc-Feraud, L., Aubert, G., Barlaud, M.: Two deterministic half-quadratic regularization algorithms for computed imaging. In: Proceedings of 1st International Conference on Image Processing, Austin, vol. 2, pp. 168–172. (1994)
[16]
Charbonnier P, Blanc-Feraud L, Aubert G, and Barlaud M Deterministic edge-preserving regularization in computed imaging IEEE Trans. Image Process. 1997 6 298-311
[17]
Clarke FH Optimization and Nonsmooth Analysis 1990 Philadelphia Classics in Applied Mathematics, SIAM
[18]
Geman S and Geman D Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images IEEE Trans. Pattern Anal. Mach. Intell. PAMI 1984 6 721-741
[19]
Hampel FR, Ronchetti EM, Rousseeuw PJ, and Stahel WA Robust Statistics: The Approach Based on Influence Functions 1986 London Wiley
[20]
Geman D and Yang C Nonlinear image recovery with half-quadratic regularization IEEE Trans. Image Process. 1995 4 7 932-946
[21]
Le Thi HA and Pham DT Difference of convex functions algorithms (DCA) for image restoration via a Markov random field model Optim. Eng. 2017 18 4 873-906
[22]
Le Thi HA and Pham DT Convex analysis approach to D.C. programming: theory, algorithms and applications Acta Mthematics Vietnamica 1997 22 1 289-355
[23]
Le Thi HA and Pham DT DC programming and DCA: thirty years of developments Math. Progr. Ser. B 2018 169 5-68
[24]
Li G and Pong TK Calculus of the exponent of Kurdyka–Lojasiewicz inequality and its applications to linear convergence of first-order methods Found. Comput. Math. 2018 18 1199-1232
[25]
Li P, Chen W, Ge H, and Ng KM - minimization methods for signal and image reconstruction with impulsive noise removal Inverse Prob. 2020 36 055009
[26]
Lou Y, Zeng T, Osher S, and Xin J A weighted difference of anisotropic and isotropic total variation model for image processing SIAM J. Imaging Sci. 2015 8 1798-823
[27]
Luo, X.-D., Luo, Z.-Q.: Extension of Hoffman’s error bound to polynomial systems. SIAM J. Optim. 4(2), 383–392 (1994).
[28]
Mordukhovich B Variational analysis and generalized differentiation I: Basic theory, Grundlehren der Mathematischen, Wissenschaften 1998 Heidelberg Springer
[29]
Mumford D and Desolneux A Pattern Theory: The Stochastic Analysis of Real-World Signals 2010 Natick A K Peters, Ltd.
[30]
Mumford, D., Shah, J.: Boundary detection by minimizing functionals, I. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, San Francisco (1985)
[31]
Mumford D and Shah J Optimal approximation by piecewise smooth functions and associated variational problems Commun. Pure Appl. Math. 1989 42 577-684
[32]
Nikolova M Markovian reconstruction using a GNC approach IEEE Trans. Image Process. 1999 8 9 1204-1220
[33]
Nikolova M and Ng MK Analysis of half-quadratic minimization methods for signal and image recovery SIAM J. Sci. Comput. 2005 27 3 937-966
[34]
Rockafellar RT Convex Analysis 1970 Princeton Princeton University
[35]
Rockafellar, R.T., Wets, R.: Variational Analysis. Grundlehren der Mathematischen, Wissenschaften, vol. 317, Springer, Heidelberg (1998)
[36]
Saad Y Iterative Methods for Sparse Linear Systems 2003 2 University City Society for Industrial and Applied Mathematics
[37]
Scholtes S Introduction to Piecewise Differentiable Equations 2012 New York Springer
[38]
Strekalovskiy, E., Cremers, D.: Real-time minimization of the piecewise smooth Mumford–Shah functional, In: Fleet, D., Pajdla, T., Schiele, B., Tuytelaars, T. (eds) Computer Vision-ECCV: ECCV 2014. Lecture Notes in Computer Science, vol. 8690. Springer, Cham (2014)
[39]
Wen B, Chen X, and Pong TK A proximal difference-of-convex algorithm with extrapolation Comput. Optim. Appl. 2018 69 297-324
[40]
Winkler G Image Analysis, Random Fields and Markov Chain Monte Carlo Methods : A Mathematical Introduction 2003 Second Berlin, Heidelberg Springer
[41]
Yuille AL and Rangarajan A The concave-convex procedure Neural Comput. 2003 15 4 915-936
[42]
Wu C, Liu Z, and Wen S A general truncated regularization framework for contrast-preserving variational signal and image restoration: motivation and implementation Sci. China Math. 2018 61 9 1711-1732
Recommendations
A Proximal Quasi-Newton Trust-Region Method for Nonsmooth Regularized Optimization
We develop a trust-region method for minimizing the sum of a smooth term (f) and a nonsmooth term (h), both of which can be nonconvex. Each iteration of our method minimizes a possibly nonconvex model of (f + h) in a trust region. The model coincides with (...
A Proximal Point Analysis of the Preconditioned Alternating Direction Method of Multipliers
We study preconditioned algorithms of alternating direction method of multipliers type for nonsmooth optimization problems. The alternating direction method of multipliers is a popular first-order method for general constrained optimization problems. ...
A proximal trust-region method for nonsmooth optimization with inexact function and gradient evaluations
AbstractMany applications require minimizing the sum of smooth and nonsmooth functions. For example, basis pursuit denoising problems in data science require minimizing a measure of data misfit plus an -regularizer. Similar problems arise in the optimal ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.
Publisher
Plenum Press
United States
Publication History
Published: 01 August 2021
Accepted: 09 June 2021
Revision received: 06 June 2021
Received: 06 January 2020
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in