×

zbMATH — the first resource for mathematics

Iterative regularization via dual diagonal descent. (English) Zbl 1425.94013
Summary: In the context of linear inverse problems, we propose and study a general iterative regularization method allowing to consider large classes of data-fit terms and regularizers. The algorithm we propose is based on a primal-dual diagonal descent method. Our analysis establishes convergence as well as stability results. Theoretical findings are complemented with numerical experiments showing state-of-the-art performances.

MSC:
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
Software:
NESTA; TIGRA; UNLocBoX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alart, P; Lemaire, B, Penalization in non-classical convex programming via variational convergence, Math. Program., 51, 307-331, (1991) · Zbl 0748.90051
[2] Alvarez, F; Cominetti, R, Primal and dual convergence of a proximal point exponential penalty method for linear programming, Math. Program., 93, 87-96, (2002) · Zbl 1007.90048
[3] Attouch, H, Viscosity solutions of minimization problems, SIAM J. Optim., 6, 769-806, (1996) · Zbl 0859.65065
[4] Attouch, H., Cabot, A., Czarnecki, M.-O.: Asymptotic behavior of non-autonomous monotone and subgradient evolution equations. arXiv:1601.00767 (2016) · Zbl 1380.34094
[5] Attouch, H; Czarnecki, M-O, Asymptotic behavior of coupled dynamical systems with multiscale aspects, J. Differ. Equ., 248, 1315-1344, (2010) · Zbl 1190.37090
[6] Attouch, H; Czarnecki, M-O; Peypouquet, J, Prox-penalization and splitting methods for constrained variational problems, SIAM J. Optim., 21, 149-173, (2011) · Zbl 1229.90225
[7] Attouch, H; Czarnecki, M-O; Peypouquet, J, Coupling forward-backward with penalty schemes and parallel splitting for constrained variational inequalities, SIAM J. Optim., 21, 1251-1274, (2011) · Zbl 1233.37063
[8] Auslender, A; Crouzeix, J-P; Fedit, P, Penalty-proximal methods in convex programming, J. Optim. Theory Appl., 55, 1-21, (1987) · Zbl 0622.90065
[9] Bachmayr, M; Burger, M, Iterative total variation schemes for nonlinear inverse problems, Inverse Probl., 25, 105004, (2009) · Zbl 1188.49028
[10] Bahraoui, MA; Lemaire, B, Convergence of diagonally stationary sequences in convex optimization, Set-Valued Anal., 2, 49-61, (1994) · Zbl 0810.65055
[11] Bakushinsky, A.B., Kokurin, MYu.: Iterative Methods for Approximate Solution of Inverse Problems. Springer, New York (2004) · Zbl 1070.65038
[12] Bauschke, HH; Borwein, J, Joint and separate convexity of the Bregman distance, inherently parallel algorithms in feasibility and optimization and their applications, Stud. Comput. Math., 8, 23-36, (2001) · Zbl 1160.65319
[13] Bauschke, H.H., Combettes, P.: Convex Analysis and Monotone Operator Theory. Springer, New York (2011) · Zbl 1218.47001
[14] Beck, A; Sabach, S, A first order method for finding minimal norm-like solutions of convex optimization problems, Math. Program., 147, 25-46, (2014) · Zbl 1297.90079
[15] Beck, A; Teboulle, M, Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett., 31, 167-175, (2003) · Zbl 1046.90057
[16] Becker, S; Bobin, J; Candès, E, NESTA: a fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci., 4, 1-39, (2011) · Zbl 1209.90265
[17] Bertero, M., Boccacci, P.: Introduction to Inverse Problems in Imaging. IOP Publishing, Bristol (1998) · Zbl 0914.65060
[18] Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.: From error bounds to the complexity of first-order descent methods for convex functions. arXiv:1510.08234 (2015) · Zbl 1373.90076
[19] Bot, RI; Hofmann, B, The impact of a curious type of smoothness conditions on convergence rates in l1-regularization, Eurasian J. Math. Comput. Appl., 1, 29-40, (2013)
[20] Bot, RI; Hein, T, Iterative regularization with a general penalty term: theory and application to L1 and TV regularization, Inverse Prob., 28, 1-19, (2012) · Zbl 1269.47054
[21] Boyer, R.: Quelques algorithmes diagonaux en optimisation convexe. Ph.D., Université de Provence (1974) · Zbl 0363.90068
[22] Bredies, K; Kunisch, K; Pock, T, Total generalized variation, SIAM J. Imaging Sci., 3, 492-526, (2010) · Zbl 1195.49025
[23] Briceño-Arias, L; Combettes, PL, A monotone + skew splitting model for composite monotone inclusions in duality, SIAM J. Optim., 21, 1230-1250, (2011) · Zbl 1239.47053
[24] Bruck, RE, A strongly convergent iterative solution of \(0 ∈ U(x)\) for a maximal monotone operator \(U\) in Hilbert space, J. Math. Anal. Appl., 48, 114-126, (1974) · Zbl 0288.47048
[25] Burger, M., Osher, S. (ed.): A guide to the TV zoo. In: Level Set and PDE Based Reconstruction Methods in Imaging, pp. 1-70. Springer, Berlin (2013) · Zbl 1342.94014
[26] Burger, M; Resmerita, E; He, L, Error estimation for Bregman iterations and inverse scale space methods in image restoration, Comput., 81, 109-135, (2007) · Zbl 1147.68790
[27] Cabot, A, The steepest descent dynamical system with control. applications to constrained minimization, ESAIM Control Optim. Calc. Var., 10, 243-258, (2004) · Zbl 1072.49004
[28] Cabot, A, Proximal point algorithm controlled by a slowly vanishing term: applications to hierarchical minimization, SIAM J. Optim., 15, 555-572, (2005) · Zbl 1079.90098
[29] Calatroni, L., De Los Reyes, J.-C., Schönlieb, C.-B.: Infimal convolution of data discrepancies for mixed noise removal. arXiv:1611.00690 (2016) · Zbl 1190.37090
[30] Chaux, C; Combettes, PL; Pesquet, J-C; Wajs, V, A variational formulation for frame-based inverse problems, Inverse Probl., 23, 1495-1518, (2007) · Zbl 1141.65366
[31] Chambolle, A; Lions, PL, Image recovery via total variation minimization and related problems, Numer. Math., 76, 167-188, (1997) · Zbl 0874.68299
[32] Chambolle, A; Pock, T, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 120-145, (2011) · Zbl 1255.68217
[33] Chambolle, A., Pock, T.: A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions, preprint hal-01099182v2 (2015) · Zbl 1179.94031
[34] Combettes, PL; Butnariu, D (ed.); Censor, Y (ed.); Reich, S (ed.), Quasi-fejérian analysis of some optimization algorithms, 115-152, (2001), New York · Zbl 0992.65065
[35] Combettes, PL; Dũng, D; Vũ, BC, Dualization of signal recovery problems, Set-Valued Var. Anal., 18, 373-404, (2010) · Zbl 1229.90123
[36] 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, pp. 185-212. Springer, New York (2011) · Zbl 1242.90160
[37] Combettes, PL; Pesquet, J-C, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Anal., 20, 307-330, (2012) · Zbl 1284.47043
[38] Combettes, PL; Wajs, V, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 1168-1200, (2005) · Zbl 1179.94031
[39] Cominetti, R; Peypouquet, J; Sorin, S, Strong asymptotic convergence of evolution equations governed by maximal monotone operators with Tikhonov regularization, J. Differ. Equ., 245, 3753-3763, (2008) · Zbl 1169.34045
[40] Cominetti, R, Coupling the proximal point algorithm with approximation methods, J. Optim. Theory Appl., 95, 581-600, (1997) · Zbl 0902.90129
[41] Czarnecki, M.-O., Noun, N., Peypouquet, J.: Splitting forward-backward penalty scheme for constrained variational problems. arXiv:1408.0974 (2014) · Zbl 1380.49009
[42] Daubechies, I; Defrise, M; Mol, C, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., 57, 1413-1457, (2004) · Zbl 1077.65055
[43] Deledalle, C-A; Vaiter, S; Fadili, J-M; Peyré, G, Stein unbiased gradient estimator of the risk (SUGAR) for multiple parameter selection, SIAM J. Imaging Sci., 7, 2448-2487, (2014) · Zbl 1361.94012
[44] Dontchev, A., Zolezzi, T.: Well-Posed Optimization Problems. Springer, Berlin (1993) · Zbl 0797.49001
[45] Dupé, F-X; Fadili, J; Starck, J-L, Deconvolution under Poisson noise using exact data-fit function and synthesis or analysis sparsity priors, Stat. Methodol., 9, 4-18, (2012) · Zbl 1248.94042
[46] Engl, H., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996) · Zbl 0859.65054
[47] Hale, E; Yin, W; Zhang, Y, Fixed-point continuation for \(ℓ _1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 1107-1130, (2008) · Zbl 1180.65076
[48] Hintermüller, M; Langer, A, Subspace correction methods for a class of non-smooth and non-additive convex variational problems with mixed \(ℓ ^1/ℓ ^2\) data-fidelity in image processing, SIAM J. Imaging Sci., 6, 2134-2173, (2013) · Zbl 1279.68327
[49] Kaltenbacher, B., Neubauer, A., Scherzer, O.: Iterative Regularization Methods for Nonlinear Ill-Posed Problems. De Gruyter, Berlin (2008) · Zbl 1145.65037
[50] Kaplan, AA, On convex programming with internal regularization, Sov. Math. Dokl. Akad. Nauk, 19, 795-799, (1975) · Zbl 0423.90061
[51] Kaplan, AA, Iteration processes of convex programming with internal regularization, Sib. Math. J., 20, 219-226, (1979) · Zbl 0459.90070
[52] Langer, A, Automated parameter selection for total variation minimization in image restoration, J. Math. Imaging Vis., 57, 239-268, (2017) · Zbl 1369.94030
[53] Le, T; Chartran, R; Asaki, T, A variational approach to reconstructing images corrupted by Poisson noise, J. Math. Imaging Vis., 27, 257-63, (2007)
[54] Lemaire, B, Coupling optimization methods and variational convergence, Trends Math. Optim. Int. Ser. Numer. Math., 84, 163-179, (1988) · Zbl 0633.49010
[55] Lemaire, B, On the convergence of some iterative methods for convex minimization, Recent Dev. Optim. Lect. Notes Econ. Math. Syst., 429, 252-268, (1995) · Zbl 0844.90066
[56] Lemaire, B, Well-posedness, conditioning and regularization of minimization, inclusion and fixed-point problems, Pliska Studia Mathematica Bulgarica, 12, 71-84, (1998) · Zbl 0947.65072
[57] Mallat, S.: A Wavelet Tour of Signal Processing, 3rd edn. Elsevier/Academic Press, Amsterdam (2009) · Zbl 1170.94003
[58] Martinet, B, Perturbation des mthodes d’optimisation. applications, R.A.I.R.O Analyse numrique, 12, 153-171, (1978) · Zbl 0379.90088
[59] Matet, S., Rosasco, L., Villa, S., Vũ, B. C.: Don’t relax: early stopping for convex regularization. arXiv:1707.05422 (2016)
[60] Nikolova, M, Minimizers of cost-functions involving non- smooth data-fidelity terms. application to the processing of outliers, SIAM J. Numer. Anal., 40, 965-994, (2002) · Zbl 1018.49025
[61] Peypouquet, J, Coupling the gradient method with a general exterior penalization scheme for convex minimization, J. Optim. Theory Appl., 153, 123-138, (2011) · Zbl 1247.90214
[62] Peypouquet, J.: Convex Optimization in Normed Spaces. Theory, Methods and Examples. Springer, New York (2015) · Zbl 1322.90004
[63] Ramlau, R, TIGRA—an iterative algorithm for regularizing nonlinear ill-posed problems, Inverse Prob., 19, 433-465, (2003) · Zbl 1029.65059
[64] Rudin, L; Osher, S; Fatemi, E, Nonlinear total variation based noise removal algorithms, Physica D, 60, 259-268, (1992) · Zbl 0780.49028
[65] Scherzer, O, A modified Landweber iteration for solving parameter estimation problems, Appl. Math. Optim., 38, 45-68, (1998) · Zbl 0915.65054
[66] Stein, C, Estimation of the mean of a multivariate normal distribution, Ann. Stat., 9, 1135-1151, (1981) · Zbl 0476.62035
[67] Steinwart, I., Christmann, A.: Support Vector Machines. Springer, New York (2008) · Zbl 1203.68171
[68] Tossings, P, The perturbed tikhonov’s algorithm and some of its applications, ESAIM Math. Model. Numer. Anal., 28, 189-221, (1994) · Zbl 0821.65036
[69] Tseng, P, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J. Control Optim., 29, 119-138, (1991) · Zbl 0737.90048
[70] Uzawa, H.: Iterative Methods for Concave Programming. Studies in Linear and Nonlinear Programming. Stanford University Press, Stanford (1958)
[71] Vainberg, M.M.: Le problème de la minimisation des fonctionelles non linéaires. C.I.M.E. IV ciclo (1970) · Zbl 1018.49025
[72] Yamada, I., Yukawa, M., Yamagishi, M.: Minimizing the Moreau envelope of nonsmooth convex functions over the fixed point set of certain quasi-nonexpansive mappings. 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, New York (2011) · Zbl 1263.47088
[73] Zolezzi, T, On equiwellset minimum problems, Appl. Math. Optim., 4, 209-223, (1978) · Zbl 0381.90105
[74] Zou, Z; Hastie, T, Regularization and variable selection via the elastic net, J. R. Stat. Soc. B, 67, 301-320, (2005) · Zbl 1069.62054
[75] Zalinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002) · Zbl 1023.46003
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.