Revisiting linearized Bregman iterations under Lipschitz-like convexity condition

Zhang, Hui; Zhang, Lu; Yang, Hao-Xing

doi:10.1090/mcom/3792

Revisiting linearized Bregman iterations under Lipschitz-like convexity condition
HTML articles powered by AMS MathViewer

by Hui Zhang, Lu Zhang and Hao-Xing Yang;

Math. Comp. 92 (2023), 779-803

DOI: https://doi.org/10.1090/mcom/3792

Published electronically: October 28, 2022

HTML | PDF | Request permission

Abstract:

The linearized Bregman iterations (LBreI) and its variants have received considerable attention in signal/image processing and compressed sensing. Recently, LBreI has been extended to a larger class of nonconvex functions, along with several theoretical issues left for further investigation. In particular, the Lipschitz gradient continuity assumption precludes its use in many practical applications. In this study, we propose a generalized algorithmic framework to unify LBreI-type methods. Our main discovery is that the Lipschitz gradient continuity assumption can be replaced by a Lipschitz-like convexity condition in both convex and nonconvex cases. As a by-product, a class of bilevel optimization problems can be solved in the proposed framework, which extends the main result made by Cai et al. [Math. Comp. 78 (2009), pp. 2127–2136]. At last, provably convergent iterative schemes on modified linear/quadratic inverse problems illustrate our finding.

References

Heinz H. Bauschke, Jérôme Bolte, and Marc Teboulle, A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications, Math. Oper. Res. 42 (2017), no. 2, 330–348. MR 3651994, DOI 10.1287/moor.2016.0817
Heinz H. Bauschke and Jonathan M. Borwein, Legendre functions and the method of random Bregman projections, J. Convex Anal. 4 (1997), no. 1, 27–67. MR 1459881
Amir Beck, First-order methods in optimization, MOS-SIAM Series on Optimization, vol. 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2017. MR 3719240, DOI 10.1137/1.9781611974997.ch1
Amir Beck and Shoham Sabach, A first order method for finding minimal norm-like solutions of convex optimization problems, Math. Program. 147 (2014), no. 1-2, Ser. A, 25–46. MR 3258517, DOI 10.1007/s10107-013-0708-2
Martin Benning, Marta M. Betcke, Matthias J. Ehrhardt, and Carola-Bibiane Schönlieb, Choose your path wisely: gradient descent in a Bregman distance framework, SIAM J. Imaging Sci. 14 (2021), no. 2, 814–843. MR 4275495, DOI 10.1137/20M1357500
Martin Benning, Christoph Brune, Martin Burger, and Jahn Müller, Higher-order TV methods—enhancement via Bregman iteration, J. Sci. Comput. 54 (2013), no. 2-3, 269–310. MR 3011360, DOI 10.1007/s10915-012-9650-3
Jérôme Bolte, Shoham Sabach, and Marc Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program. 146 (2014), no. 1-2, Ser. A, 459–494. MR 3232623, DOI 10.1007/s10107-013-0701-9
Jérôme Bolte, Shoham Sabach, Marc Teboulle, and Yakov Vaisbourd, First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems, SIAM J. Optim. 28 (2018), no. 3, 2131–2151. MR 3832977, DOI 10.1137/17M1138558
L. M. Brègman, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 620–631 (Russian). MR 215617
Martin Burger, Guy Gilboa, Stanley Osher, and Jinjun Xu, Nonlinear inverse scale space methods, Commun. Math. Sci. 4 (2006), no. 1, 179–212. MR 2204083, DOI 10.4310/CMS.2006.v4.n1.a7
Jian-Feng Cai, Emmanuel J. Candès, and Zuowei Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim. 20 (2010), no. 4, 1956–1982. MR 2600248, DOI 10.1137/080738970
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515–1536. MR 2501061, DOI 10.1090/S0025-5718-08-02189-3
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sci. 2 (2009), no. 1, 226–252. MR 2486529, DOI 10.1137/080733371
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Convergence of the linearized Bregman iteration for $\ell _1$-norm minimization, Math. Comp. 78 (2009), no. 268, 2127–2136. MR 2521281, DOI 10.1090/S0025-5718-09-02242-X
Gong Chen and Marc Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM J. Optim. 3 (1993), no. 3, 538–543. MR 1230155, DOI 10.1137/0803026
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev. 43 (2001), no. 1, 129–159. Reprinted from SIAM J. Sci. Comput. 20 (1998), no. 1, 33–61 (electronic) [ MR1639094 (99h:94013)]. MR 1854649, DOI 10.1137/S003614450037906X
Krzysztof C. Kiwiel, Free-steering relaxation methods for problems with strictly convex costs and linear constraints, Math. Oper. Res. 22 (1997), no. 2, 326–349. MR 1450795, DOI 10.1287/moor.22.2.326
J. Darbon and S. Osher, Fast discrete optimization for sparse approximations and deconvolutions, 2007, preprint.
Krzysztof C. Kiwiel, Proximal minimization methods with generalized Bregman functions, SIAM J. Control Optim. 35 (1997), no. 4, 1142–1168. MR 1453294, DOI 10.1137/S0363012995281742
Ming-Jun Lai and Wotao Yin, Augmented $\ell _1$ and nuclear-norm models with a globally linearly convergent algorithm, SIAM J. Imaging Sci. 6 (2013), no. 2, 1059–1091. MR 3062582, DOI 10.1137/120863290
Dirk A. Lorenz, Frank Schöpfer, and Stephan Wenger, The linearized Bregman method via split feasibility problems: analysis and generalizations, SIAM J. Imaging Sci. 7 (2014), no. 2, 1237–1262. MR 3215060, DOI 10.1137/130936269
Haihao Lu, Robert M. Freund, and Yurii Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim. 28 (2018), no. 1, 333–354. MR 3759881, DOI 10.1137/16M1099546
D. R. Luke, Phase retrieval, what’s new?, SIAG/OPTViewsNews 25 (2017), 1–5.
Michael Moeller, Eva-Maria Brinkmann, Martin Burger, and Tamara Seybold, Color Bregman TV, SIAM J. Imaging Sci. 7 (2014), no. 4, 2771–2806. MR 3534003, DOI 10.1137/130943388
Arkadi Nemirovski, Prox-method with rate of convergence $O(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim. 15 (2004), no. 1, 229–251. MR 2112984, DOI 10.1137/S1052623403425629
Stanley Osher, Martin Burger, Donald Goldfarb, Jinjun Xu, and Wotao Yin, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul. 4 (2005), no. 2, 460–489. MR 2162864, DOI 10.1137/040605412
Boris T. Polyak, Introduction to optimization, Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York, 1987. Translated from the Russian; With a foreword by Dimitri P. Bertsekas. MR 1099605
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970. MR 274683, DOI 10.1515/9781400873173
Walter Rudin, Principles of mathematical analysis, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1953. MR 55409
Shoham Sabach and Shimrit Shtern, A first order method for solving convex bilevel optimization problems, SIAM J. Optim. 27 (2017), no. 2, 640–660. MR 3634996, DOI 10.1137/16M105592X
Marc Teboulle, A simplified view of first order methods for optimization, Math. Program. 170 (2018), no. 1, Ser. B, 67–96. MR 3816558, DOI 10.1007/s10107-018-1284-2
Jinjun Xu and Stanley Osher, Iterative regularization and nonlinear inverse scale space applied to wavelet-based denoising, IEEE Trans. Image Process. 16 (2007), no. 2, 534–544. MR 2462742, DOI 10.1109/TIP.2006.888335
Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856–877. MR 2735964, DOI 10.1137/090760350
Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143–168. MR 2475828, DOI 10.1137/070703983
Hui Zhang, New analysis of linear convergence of gradient-type methods via unifying error bound conditions, Math. Program. 180 (2020), no. 1-2, Ser. A, 371–416. MR 4062841, DOI 10.1007/s10107-018-01360-1
Hui Zhang, Lizhi Cheng, and Wotao Yin, A dual algorithm for a class of augmented convex signal recovery models, Commun. Math. Sci. 13 (2015), no. 1, 103–112. MR 3238140, DOI 10.4310/CMS.2015.v13.n1.a5
H. Zhang and Y. H. Dai, Mirror frameworks for relatively Lipschitz and monotone-like variational inequalities, arXiv:2108.12070 [math.OC], 2021.
H. Zhang and W. Yin, Gradient methods for convex minimization: better rates under weaker conditions, CAM Report 13-17, UCLA, 2013.
Xiaoqun Zhang, Martin Burger, Xavier Bresson, and Stanley Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imaging Sci. 3 (2010), no. 3, 253–276. MR 2679428, DOI 10.1137/090746379

AMS Website Down

Mathematics of Computation

Revisiting linearized Bregman iterations under Lipschitz-like convexity condition
HTML articles powered by AMS MathViewer

Abstract: