×

zbMATH — the first resource for mathematics

A proximal interior point algorithm with applications to image processing. (English) Zbl 07255781
Summary: In this article, we introduce a new proximal interior point algorithm (PIPA). This algorithm is able to handle convex optimization problems involving various constraints where the objective function is the sum of a Lipschitz differentiable term and a possibly nonsmooth one. Each iteration of PIPA involves the minimization of a merit function evaluated for decaying values of a logarithmic barrier parameter. This inner minimization is performed thanks to a finite number of subiterations of a variable metric forward-backward method employing a line search strategy. The convergence of this latter step as well as the convergence the global method itself is analyzed. The numerical efficiency of the proposed approach is demonstrated in two image processing applications.
Reviewer: Reviewer (Berlin)
MSC:
68 Computer science
94 Information and communication theory, circuits
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chan, TF; Vese, LA, Active contours without edges, IEEE Trans. Image Process., 10, 2, 266-277 (2001) · Zbl 1039.68779
[2] Briceño-Arias, L.M., Chierchia, G., Chouzenoux, E., Pesquet, J.-C.: A random block-coordinate Douglas-Rachford splitting method with low computational complexity for binary logistic regression. Comput. Optim. Appl. 1-20 (2017) · Zbl 07066001
[3] Nikolova, M., A variational approach to remove outliers and impulse noise, J. Math. Imaging Vis., 20, 1-2, 99-120 (2004) · Zbl 1366.94065
[4] Wright, M.H.: Interior methods for constrained optimization. Acta Numer., pp. 341-407 (1991) · Zbl 0766.65053
[5] Forsgren, A.; Gill, PE; Wright, MH, Interior methods for nonlinear optimization, SIAM Rev., 44, 4, 525-597 (2002) · Zbl 1028.90060
[6] Gondzio, J., Interior point methods 25 years later, Eur. J. Oper. Res., 218, 3, 587-601 (2012) · Zbl 1244.90007
[7] Gould, NIM; Orban, D.; Sartenaer, A.; Toint, PL, Superlinear convergence of primal-dual interior point algorithms for nonlinear programming, SIAM J. Optim., 11, 4, 974-1002 (2001) · Zbl 1003.65066
[8] Johnson, CA; Seidel, J.; Sofer, A., Interior-point methodology for 3-D PET reconstruction, IEEE Trans. Med. Imaging, 19, 4, 271-285 (2000)
[9] Chouzenoux, E.; Legendre, M.; Moussaoui, S.; Idier, J., Fast constrained least squares spectral unmixing using primal-dual interior-point optimization, IEEE J. Sel. Top. Appl. Earth Observ. Remote Sens., 7, 1, 59-69 (2014)
[10] Armand, P.; Gilbert, J-C; Jan-Jégou, S., A feasible BFGS interior point algorithm for solving convex minimization problems, SIAM J. Optim., 11, 1, 199-222 (2000) · Zbl 0990.90092
[11] Bonettini, S.; Serafini, T., Non-negatively constrained image deblurring with an inexact interior point method, J. Comput. Appl. Math., 231, 1, 236-248 (2009) · Zbl 1167.94003
[12] Ahmad, R.; Schniter, P., Iteratively reweighted \(\ell_1\) approaches to sparse composite regularization, IEEE Trans. Comput. Imaging, 1, 4, 220-235 (2015)
[13] Osher, S.; Solé, A.; Vese, L., Image decomposition and restoration using total variation minimization and the \({H}^{-1}\) norm, Multiscale Model. Simul., 1, 3, 349-370 (2003) · Zbl 1051.49026
[14] Fu, H.; Ng, MK; Nikolova, M.; Barlow, JL, Efficient minimization methods of mixed \(\ell 2-\ell 1\) and \(\ell 1-\ell 1\) norms for image restoration, SIAM J. Sci. Comput., 27, 6, 1881-1902 (2006) · Zbl 1103.65044
[15] Kim, S-J; Koh, K.; Lustig, M.; Boyd, S.; Gorinevsky, D., An interior-point method for large-scale \(\ell_1 \)-regularized least squares, IEEE J. Sel. Top. Signal Process., 1, 4, 606-617 (2007)
[16] Fountoulakis, K.; Gondzio, J., Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems, Comput. Optim. Appl., 65, 3, 605-635 (2016) · Zbl 1357.90107
[17] Combettes, P.-L., Pesquet, J.-C.: Proximal splitting methods in signal processing. In: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185-212. Springer, Berlin (2011) · Zbl 1242.90160
[18] Combettes, P-L; Wajs, VR, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 4, 1168-1200 (2005) · Zbl 1179.94031
[19] Chen, GHG; Rockafellar, RT, Convergence rates in forward-backward splitting, SIAM J. Optim., 7, 2, 421-444 (1997) · Zbl 0876.49009
[20] Combettes, PL; Vũ, BC, Variable metric forward-backward splitting with applications to monotone inclusions in duality, Optimization, 63, 9, 1289-1318 (2014) · Zbl 1309.90109
[21] 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) · Zbl 1318.90058
[22] Frankel, P.; Garrigos, G.; Peypouquet, J., Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, J. Optim. Theory Appl., 165, 3, 874-900 (2015) · Zbl 1316.49039
[23] Łojasiewicz, S., Une propriété topologique des sous-ensembles analytiques réels, Les équations aux dérivées partielles, 117, 87-89 (1963)
[24] Kurdyka, K., On gradients of functions definable in o-minimal structures, Ann. de l’institut Fourier, 48, 769-783 (1998) · Zbl 0934.32009
[25] Bolte, J.; Daniilidis, A.; Lewis, A., The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 4, 1205-1223 (2007) · Zbl 1129.26012
[26] Attouch, H.; Bolte, J., On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program. B, 116, 1, 5-16 (2009) · Zbl 1165.90018
[27] Attouch, H.; Bolte, J.; Svaiter, BF, 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) · Zbl 1260.49048
[28] Kaplan, A.; Tichatschke, R., Proximal methods in view of interior-point strategies, J. Optim. Theory Appl., 98, 2, 399-429 (1998) · Zbl 0908.90210
[29] Valkonen, T.: Interior-proximal primal-dual methods. arXiv preprintarXiv:1706.07067 (2017) · Zbl 1369.49040
[30] Chouzenoux, E.; Moussaoui, S.; Idier, J., Majorize-minimize linesearch for inversion methods involving barrier function optimization, Inverse Probl., 28, 6, 065011 (2012) · Zbl 1256.65051
[31] Tseng, P.; Yun, S., A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117, 1-2, 387-423 (2009) · Zbl 1166.90016
[32] Bello Cruz, JY; Nghia, TTA, On the convergence of the forward-backward splitting method with linesearches, Optim. Methods Softw., 31, 6, 1209-1238 (2016) · Zbl 1354.65116
[33] 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) · Zbl 1338.65157
[34] Salzo, S., The variable metric forward-backward splitting algorithm under mild differentiability assumptions, SIAM J. Optim., 27, 4, 2153-2181 (2017) · Zbl 1375.65085
[35] Bonettini, S.; Prato, M., New convergence results for the scaled gradient projection method, Inverse Probl., 31, 9, 095008 (2015) · Zbl 1333.90124
[36] Rockafellar, RT; Wets, RJ-B, Variational Analysis (2009), Berlin: Springer, Berlin
[37] Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2017), Berlin: Springer, Berlin
[38] Pustelnik, N.; Chaux, C.; Pesquet, J-C, Parallel proximal algorithm for image restoration using hybrid regularization, IEEE Trans. Image Process., 20, 9, 2450-2462 (2011) · Zbl 1372.94213
[39] Lee, J.D., Recht, B., Srebro, N., Tropp, J., Salakhutdinov, R.R.: Practical large-scale optimization for max-norm regularization. In: 23rd Advances in Neural Information Processing Systems (NIPS), pp. 1297-1305, Vancouver, Canada (2010)
[40] Combettes, P-L; Dũng, D.; Vũ, BC, Proximity for sums of composite functions, J. Math. Anal. Appl., 380, 2, 680-688 (2011) · Zbl 1223.47120
[41] 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) · Zbl 1382.94004
[42] Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 1-2, 459-494 (2014) · Zbl 1297.90125
[43] Li, G.; Pong, TK, Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods, Found. Comput. Math., 18, 5, 1199-1232 (2018) · Zbl 1405.90076
[44] 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) · Zbl 1214.65036
[45] Harizanov, S., Pesquet, J.-C., Steidl, G.: Epigraphical projection for solving least squares Anscombe transformed constrained optimization problems. In: 4th International Conference on Scale Space and Variational Methods in Computer Vision (SSVM), pp. 125-136, Schloss Seggau, Graz, Austria (2013). Springer · Zbl 1382.94014
[46] Musse, O.; Heitz, F.; Armspach, J-P, Topology preserving deformable image matching using constrained hierarchical parametric models, IEEE Trans. Image Process., 10, 7, 1081-1093 (2001) · Zbl 1036.68621
[47] Klodt, M., Cremers, D.: A convex framework for image segmentation with moment constraints. In: 13th IEEE International Conference on Computer Vision (ICCV), pp. 2236-2243. Sydney, Australia (2011)
[48] Chouzenoux, E.; Pesquet, J-C; Repetti, A., A block coordinate variable metric forward-backward algorithm, J. Glob. Optim., 66, 3, 457-485 (2016) · Zbl 1351.90128
[49] Attouch, H.; Czarnecki, M-O; Peypouquet, J., Prox-penalization and splitting methods for constrained variational problems, SIAM J. Optim., 21, 1, 149-173 (2011) · Zbl 1229.90225
[50] Garrigos, G.; Rosasco, L.; Villa, S., Iterative regularization via dual diagonal descent, J. Math. Imaging Vis., 60, 2, 189-215 (2018) · Zbl 1425.94013
[51] Attouch, H.; Cabot, A.; Czarnecki, M-O, Asymptotic behavior of nonautonomous monotone and subgradient evolution equations, Trans. Am. Math. Soc., 370, 2, 755-790 (2018) · Zbl 1380.34094
[52] Attouch, H.; Czarnecki, M-O; Peypouquet, J., Coupling forward-backward with penalty schemes and parallel splitting for constrained variational inequalities, SIAM J. Optim., 21, 4, 1251-1274 (2011) · Zbl 1233.37063
[53] Alvarez, F.; Cabot, A., Asymptotic selection of viscosity equilibria of semilinear evolution equations by the introduction of a slowly vanishing term, Discrete Contin. Dyn. Syst., 15, 3, 921 (2006) · Zbl 1115.35020
[54] Cabot, A., Proximal point algorithm controlled by a slowly vanishing term: applications to hierarchical minimization, SIAM J. Optim., 15, 2, 555-572 (2005) · Zbl 1079.90098
[55] Iusem, AN; Svaiter, BF; Teboulle, M., Entropy-like proximal methods in convex programming, Math. Oper. Res., 19, 4, 790-814 (1994) · Zbl 0821.90092
[56] Brito, AS; da Cruz Neto, JX; Lopes, JO; Oliveira, PR, Interior proximal algorithm for quasiconvex programming problems and variational inequalities with linear constraints, J. Optim. Theory Appl., 154, 1, 217-234 (2012) · Zbl 1273.90238
[57] Quiroz, EAP; Ramirez, LM; Oliveira, PR, An inexact proximal method for quasiconvex minimization, Eur. J. Oper. Res., 246, 3, 721-729 (2015) · Zbl 1346.90689
[58] Pustelnik, N., Benazza-Benhayia, A., Zheng, Y., Pesquet, J.-C.: Wavelet-based image deconvolution and reconstruction. In: Wiley Encyclopedia of Electrical and Electronics Engineering, pp. 1-34 (1999)
[59] Chaux, C., Benazza-Benyahia, A., Pesquet, J.-C., Duval, L.: Wavelet transform for the denoising of multivariate images. In: Collet, C., Chanussot, J., Chehdi, K. (eds.) Multivariate Image Processing, pp. 203-237. ISTE Ltd and Wiley (2010)
[60] Rudin, LI; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, 1-4, 259-268 (1992) · Zbl 0780.49028
[61] Hastie, T.; Tibshirani, R.; Friedman, JH, The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2009), Berlin: Springer, Berlin · Zbl 1273.62005
[62] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[63] Huang, Y.; Dong, Y., New properties of forward-backward splitting and a practical proximal-descent algorithm, Appl. Math. Comput., 237, 60-68 (2014) · Zbl 1336.65101
[64] Bonnans, J-F; Gilbert, J-C; Lemaréchal, C.; Sagastizábal, CA, Numerical Optimization: Theoretical and Practical Aspects (2006), Berlin: Springer, Berlin
[65] Corbineau, M.-C., Chouzenoux, E., Pesquet, J.-C.: PIPA: a new proximal interior point algorithm for large-scale convex optimization. In: 43rd IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1343-1347. Calgary, Canada (2018a)
[66] Corbineau, M.-C., Chouzenoux, E., Pesquet, J.-C.: Geometry-texture decomposition/reconstruction using a proximal interior point algorithm. In: 10th IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM), pp. 435-439, Sheffield, UK (2018b)
[67] Bioucas-Dias, JM; Plaza, A.; Dobigeon, N.; Parente, M.; Du, Q.; Gader, P.; Chanussot, J., Hyperspectral unmixing overview: geometrical, statistical, and sparse regression-based approaches, IEEE J. Sel. Top. Appl. Earth Observ. Remote Sens., 5, 2, 354-379 (2012)
[68] Chan, R.H., Kan, K.K., Nikolova, M., Plemmons, R.J.: A two-stage method for spectral-spatial classification of hyperspectral images. arXiv preprintarXiv:1806.00836 (2018)
[69] Iordache, M-D; Bioucas-Dias, JM; Plaza, A., Total variation spatial regularization for sparse hyperspectral unmixing, IEEE Trans. Geosci. Remote Sens., 50, 11, 4484-4502 (2012)
[70] Keshava, N.; Mustard, JF, Spectral unmixing, IEEE Signal Process. Mag., 19, 1, 44-57 (2002)
[71] Becker, S., Fadili, J.: A quasi-Newton proximal splitting method. In: 25th Advances in Neural Information Processing Systems (NIPS), pp. 2618-2626, Lake Tahoe, USA (2012)
[72] Setzer, S.; Steidl, G.; Teuber, T., Deblurring Poissonian images by split Bregman techniques, J. Vis. Commun. Image Represent., 21, 3, 193-199 (2010)
[73] Komodakis, N.; Pesquet, J-C, Playing with duality: an overview of recent primal-dual approaches for solving large-scale optimization problems, IEEE Signal Process. Mag., 32, 6, 31-54 (2015)
[74] Combettes, P.L., Condat, L., Pesquet, J.-C., Vũ, B.C.: A forward-backward view of some primal-dual optimization methods in image recovery. In: 21st IEEE International Conference on Image Processing (ICIP), pp. 4141-4145, Paris, France (2014)
[75] Raguet, H.; Fadili, J.; Peyré, G., A generalized forward-backward splitting, SIAM J. Imaging Sci., 6, 3, 1199-1226 (2013) · Zbl 1296.47109
[76] Shefi, R.; Teboulle, M., Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim., 24, 1, 269-297 (2014) · Zbl 1291.90176
[77] Raguet, H.; Landrieu, L., Preconditioning of a generalized forward-backward splitting and application to optimization on graphs, SIAM J. Imaging Sci., 8, 4, 2706-2739 (2015) · Zbl 1338.47120
[78] Frecon, J., Pustelnik, N., Wendt, H., Condat, L., Abry, P.: Multifractal-based texture segmentation using variational procedure. In: 12th IEEE Image, Video, and Multidimensional Signal Processing Workshop (IVMSP), pp. 1-5 (2016)
[79] Aujol, J-F; Chan, TF, Combining geometrical and textured information to perform image classification, J. Vis. Commun. Image Represent., 17, 5, 1004-1023 (2006)
[80] Bertalmio, M.; Vese, L.; Sapiro, G.; Osher, S., Simultaneous structure and texture image inpainting, IEEE Trans. Image Process., 12, 8, 882-889 (2003)
[81] Briceño-Arias, LM; Combettes, PL; Pesquet, J-C; Pustelnik, N., Proximal algorithms for multicomponent image recovery problems, J. Math. Imaging Vis., 41, 1-2, 3-22 (2011) · Zbl 1255.68213
[82] Pustelnik, N., Wendt, H., Abry, P.: Local regularity for texture segmentation: combining wavelet leaders and proximal minimization. In: 38th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5348-5352. Vancouver, Canada (2013)
[83] Haralick, RM, Statistical and structural approaches to texture, Proc. IEEE, 67, 5, 768-804 (1979)
[84] Kak, AC; Stanley, M., Principles of Computerized Tomographic Imaging (2001), Philadelphia: SIAM, Philadelphia
[85] Chouzenoux, E., Zolyniak, F., Gouillart, E., Talbot, H.: A majorize-minimize memory gradient algorithm applied to X-ray tomography. In: 20th IEEE International Conference on Image Processing (ICIP), pp. 1011-1015, Melbourne, Australia (2013)
[86] Gouillart, E.; Krzakala, F.; Mézard, M.; Zdeborová, L., Belief-propagation reconstruction for discrete tomography, Inverse Prob., 29, 3, 035003 (2013) · Zbl 1318.92030
[87] 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) · Zbl 1318.90058
[88] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 1, 120-145 (2011) · Zbl 1255.68217
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.