An \(\mathcal O(1/{k})\) convergence rate for the variable stepsize Bregman operator splitting algorithm. (English) Zbl 1381.49009
Summary: An earlier paper proved the convergence of a variable stepsize Bregman operator splitting algorithm (BOSVS) for minimizing \(\phi(Bu)+H(u)\), where \(H\) and \(\phi\) are convex functions, and \(\phi\) is possibly nonsmooth. The algorithm was shown to be relatively efficient when applied to partially parallel magnetic resonance image reconstruction problems. In this paper, the convergence rate of BOSVS is analyzed. When \(H(u)=\| Au-f\|^2\), where \(A\) is a matrix, it is shown that for an ergodic approximation \(\mathbf u_k\) obtained by averaging \(k\) BOSVS iterates, the error in the objective value \(\phi(B\mathbf u_k)+H(\mathbf u_k)\) is \(\mathcal O(1/k)\). When the optimization problem has a unique solution \(u^\ast\), we obtain the estimate \(\|\mathbf u_k-u^\ast\|=\mathcal O(1/\sqrt{k})\). The theoretical analysis is compared to observed convergence rates for partially parallel magnetic resonance image reconstruction problems where \(A\) is a large dense ill-conditioned matrix.
MSC:
| 49J40 | Variational inequalities |
| 65K10 | Numerical optimization and variational techniques |
| 65K15 | Numerical methods for variational inequalities and related problems |
| 90C25 | Convex programming |
Keywords:
nonsmooth optimization; convex optimization; BOSVS; ergodic convergence; saddle point problem; variational inequalityReferences:
| [1] | M. Afonso, J. Bioucas-Dias, and M. Figueiredo, {\it Fast image recovery using variable splitting and constrained optimization}, IEEE Trans. Image Process., 19 (2010), pp. 2345-2356. · Zbl 1371.94018 |
| [2] | J. Barzilai and J. M. Borwein, {\it Two point step size gradient methods}, IMA J. Numer. Anal., 8 (1988), pp. 141-148. · Zbl 0638.65055 |
| [3] | S. Becker, J. Bobin, and E. J. Candès, {\it NESTA: A fast and accurate first-order method for sparse recovery}, SIAM J. Imaging Sci., 4 (2011), pp. 1-39, http://dx.doi.org/10.1137/090756855. · Zbl 1209.90265 |
| [4] | K. Block, M. Uecker, and J. Frahm, {\it Undersampled radial MRI with multiple coils: Iterative image reconstruction using a total variation constraint}, Magn. Reson. Med., 57 (2007), pp. 1086-1098. |
| [5] | R. Broughton, I. Coope, P. Renaud, and R. Tappenden, {\it A box constrained gradient projection algorithm for compressed sensing}, IEEE Trans. Signal Process., 91 (2011), pp. 1985-1992. · Zbl 1217.94036 |
| [6] | R. E. Bruck, {\it On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space}, J. Math. Anal. Appl., 61 (1977), pp. 159-164. · Zbl 0423.47023 |
| [7] | T. F. Chan, G. H. Golub, and P. Mulet, {\it A nonlinear primal-dual method for total variation-based image restoration}, SIAM J. Sci. Comput., 20 (1999), pp. 1964-1977, http://dx.doi.org/10.1137/S1064827596299767. · Zbl 0929.68118 |
| [8] | Y. Chen, W. Hager, F. Huang, D. Phan, X. Ye, and W. Yin, {\it Fast algorithms for image reconstruction with application to partially parallel MR imaging}, SIAM J. Imaging Sci., 5 (2012), pp. 90-118, http://dx.doi.org/10.1137/100792688. · Zbl 1247.90212 |
| [9] | Y. Chen, W. W. Hager, M. Yashtini, X. Ye, and H. Zhang, {\it Bregman operator splitting with variable stepsize for total variation image reconstruction}, Comput. Optim. Appl., 54 (2013), pp. 317-342, doi: 10.1007/s10589-012-9519-2, http://dl.acm.org/citation.cfm?id=2436106. · Zbl 1290.90071 |
| [10] | Y. Chen, G. Lan, and Y. Ouyang, {\it Optimal primal-dual methods for a class of saddle point problems}, SIAM J. Optim., 24 (2014), pp. 1779-1814, http://dx.doi.org/10.1137/130919362. · Zbl 1329.90090 |
| [11] | Y. Chen, M. Rao, Y. Tonegawa, and T. Wunderli, {\it Partial regularity for a selective smoothing functional for image restoration in BV space}, SIAM J. Math. Anal., 37 (2005), pp. 1098-1116, http://dx.doi.org/10.1137/050623887. · Zbl 1092.49015 |
| [12] | J. Darbon and M. Sigelle, {\it A fast and exact algorithm for total variation minimization}, in Pattern Recognition and Image Analysis, J. S. Marques, N. P. de la Blanca, and P. Pina, eds., Lecture Notes in Comput. Sci. 3522, Springer-Verlag, Berlin, 2005, pp. 351-359. |
| [13] | D. Donoho, {\it Compressed sensing}, IEEE Trans. Inform. Theory, 52 (2006), pp. 351-359. · Zbl 1288.94016 |
| [14] | E. Esser, X. Zhang, and T. F. Chan, {\it A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science}, SIAM J. Imaging Sci., 3 (2010), pp. 1015-1046, http://dx.doi.org/10.1137/09076934X. · Zbl 1206.90117 |
| [15] | D. Gabay, {\it Applications of the method of multipliers to variational inequalities}, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary Value Problems, M. Fortin and R. Glowinski, eds., North Holland, Amsterdam, 1983, pp. 299-331. |
| [16] | D. Gabay and B. Mercier, {\it A dual algorithm for the solution of nonlinear variational problems via finite-element approximations}, Comput. Math. Appl., 2 (1976), pp. 17-40. · Zbl 0352.65034 |
| [17] | R. Glowinski and A. Marrocco, {\it Sur l’approximation par éléments finis d’ordre un, et la résolution par pénalisation-dualité d’une classe de problèmes de dirichlet nonlinéaires}, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér., 9 (1975), pp. 41-76. · Zbl 0368.65053 |
| [18] | T. Goldstein and S. Osher, {\it The split Bregman method for L \(1\)-regularized problems}, SIAM J. Imaging Sci., 2 (2009), pp. 323-343, http://dx.doi.org/10.1137/080725891. · Zbl 1177.65088 |
| [19] | W. W. Hager, C. Ngo, M. Yashtini, and H. Zhang, {\it An alternating direction approximate Newton algorithm for ill-conditioned inverse problems with application to parallel MRI}, J. Oper. Res. Soc. China, 3 (2015), pp. 139-162, doi:10.1007/s40305-015-0078-y, https://www.math.lsu.edu/ hozhang/papers/adan.pdf. · Zbl 1317.90235 |
| [20] | W. W. Hager, D. T. Phan, and H. Zhang, {\it Gradient-based methods for sparse recovery}, SIAM J. Imaging Sci., 4 (2011), pp. 146-165, http://dx.doi.org/10.1137/090775063. · Zbl 1209.90266 |
| [21] | E. T. Hale, W. Yin, and Y. Zhang, {\it Fixed-point continuation for \(ℓ_1\)-minimization: Methodology and convergence}, SIAM J. Optim., 19 (2008), pp. 1107-1130, http://dx.doi.org/10.1137/070698920. · Zbl 1180.65076 |
| [22] | B. He and X. Yuan, {\it On the \({O}(1/n)\) convergence rate of the Douglas-Rachford alternating direction method}, SIAM J. Numer. Anal., 50 (2012), pp. 700-709, http://dx.doi.org/10.1137/110836936. · Zbl 1245.90084 |
| [23] | Y.-M. Huang, M. K. Ng, and Y.-W. Wen, {\it A new total variation method for multiplicative noise removal}, SIAM J. Imaging Sci., 2 (2009), pp. 20-40, http://dx.doi.org/10.1137/080712593. · Zbl 1187.68655 |
| [24] | G. Lan and R. D. C. Monteiro, {\it Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Programming}, tech. report, School of ISyE, Georgia Tech, Atlanta, GA, 2009. |
| [25] | Y. Li and F. Santosa, {\it A computational algorithm for minimizing total variation in image restoration}, IEEE Trans. Image Process., 5 (1996), pp. 987-995. |
| [26] | M. Lustig, D. Donoho, and J. M. Pauly, {\it Sparse MRI: The application of compressed sensing for rapid MR imaging}, Magn. Reson. Med., 58 (2007), pp. 1182-1195. |
| [27] | R. D. C. Monteiro and B. F. Svaiter, {\it On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean}, SIAM J. Optim., 20 (2010), pp. 2755-2787, http://dx.doi.org/10.1137/090753127. · Zbl 1230.90200 |
| [28] | R. D. C. Monteiro and B. F. Svaiter, {\it Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers}, SIAM J. Optim., 23 (2013), pp. 475-507, http://dx.doi.org/10.1137/110849468. · Zbl 1267.90181 |
| [29] | A. Nemirovski, {\it Efficient Methods in Convex Programming}, tech. report, Technion – The Israel Institute of Technology, Haifa, Israel, 1994. |
| [30] | A. Nemirovski, {\it 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), pp. 229-251, http://dx.doi.org/10.1137/S1052623403425629. · Zbl 1106.90059 |
| [31] | Y. Nesterov, {\it Introductory Lectures on Convex Optimization: A Basic Course}, Appl. Optim. 87, Kluwer Academic, Boston, Dordrecht, London, 2004, http://opac.inria.fr/record=b1104789. · Zbl 1086.90045 |
| [32] | Y. E. Nesterov, {\it Smooth minimization of nonsmooth functions}, Math. Program., 103 (2005), pp. 127-152. · Zbl 1079.90102 |
| [33] | K. Pruessmann, M. Weiger, P. Bornert, and P. Boesiger, {\it Advances in sensitivity encoding with arbitrary \(k\)-space trajectories}, Magn. Reson. Med., 46 (2001), pp. 638-651. |
| [34] | R. T. Rockafellar, {\it Convex Analysis}, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401 |
| [35] | L. Rudin, S. Osher, and E. Fatemi, {\it Non-linear total variation noise removal algorithm}, Phys. D, 60 (1992), pp. 259-268. · Zbl 0780.49028 |
| [36] | R. Shefi and M. Teboulle, {\it Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization}, SIAM J. Optim., 24 (2014), pp. 269-297, http://dx.doi.org/10.1137/130910774. · Zbl 1291.90176 |
| [37] | C. R. Vogel, {\it A multigrid method for total variation-based image denoising}, in Computation and Control IV, K. Bowers and J. Lund, eds., Progr. Systems Control Theory 20, Birkhäuser, Boston, 1995, pp. 323-331. · Zbl 0831.93062 |
| [38] | C. R. Vogel and M. E. Oman, {\it Iterative methods for total variation denoising}, SIAM J. Sci. Comput., 17 (1996), pp. 227-238, http://dx.doi.org/10.1137/0917016. · Zbl 0847.65083 |
| [39] | Y. Wang, J. Yang, W. Yin, and Y. Zhang, {\it A new alternating minimization algorithm for total variation image reconstruction}, SIAM J. Imaging Sci., 1 (2008), pp. 248-272, http://dx.doi.org/10.1137/080724265. · Zbl 1187.68665 |
| [40] | S. J. Wright, R. D. Nowak, and M. A. T. Figueiredo, {\it Sparse reconstruction by separable approximation}, IEEE Trans. Signal Process., 57 (2009), pp. 2479-2493. · Zbl 1391.94442 |
| [41] | C. Wu and X.-C. Tai, {\it Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models}, SIAM J. Imaging Sci., 3 (2010), pp. 300-339, http://dx.doi.org/10.1137/090767558. · Zbl 1206.90245 |
| [42] | C. Wu, J. Zhang, and X.-C. Tai, {\it Augmented Lagrangian method for total variation restoration with non-quadratic fidelity}, Inverse Probl. Imaging, 5 (2011), pp. 237-261. · Zbl 1225.80013 |
| [43] | J. Yang, W. Yin, Y. Zhang, and Y. Wang, {\it A fast algorithm for edge-preserving variational multichannel image restoration}, SIAM J. Imaging Sci., 2 (2009), pp. 569-592, http://dx.doi.org/10.1137/080730421. · Zbl 1181.68304 |
| [44] | J. Yang, Y. Zhang, and W. Yin, {\it A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data}, IEEE J. Selected Topics Signal Process., 4 (2010), pp. 288-297. |
| [45] | M. Yashtini, W. W. Hager, Y. Chen, and X. Ye, {\it Partially parallel MR image reconstruction using sensitivity encoding}, in Proceedings of the 2012 IEEE International Conference on Image Processing, Orlando, IEEE, 2012, pp. 2077-2080. |
| [46] | X. Ye, Y. Chen, and F. Huang, {\it MR image reconstruction via sparse representation: Modeling and algorithm}, in Proceedings of the International Conference on Image Processing, Computer Vision, and Pattern Recognition (IPCV), 2009, pp. 10-16. |
| [47] | X. Ye, Y. Chen, and F. Huang, {\it Computational acceleration for MR image reconstruction in partially parallel imaging}, IEEE Trans. Med. Imaging, 30 (2011), pp. 1055-1063. |
| [48] | L. Ying, B. Liu, M. C. Steckner, G. Wu, M. Wu, and S.-J. Li, {\it A statistical approach to SENSE regularization with arbitrary k-space trajectories}, Magn. Reson. Med., 60 (2008), pp. 414-421. |
| [49] | X. Zhang, M. Burger, X. Bresson, and S. Osher, {\it Bregmanized nonlocal regularization for deconvolution and sparse reconstruction}, SIAM J. Imaging Sci., 3 (2010), pp. 253-276, http://dx.doi.org/10.1137/090746379. · Zbl 1191.94030 |
| [50] | X. Zhang, M. Burger, and S. Osher, {\it A unified primal-dual algorithm framework based on Bregman iteration}, J. Sci. Comput., 46 (2011), pp. 20-46. · Zbl 1227.65052 |
| [51] | M. Zhu and T. Chan, {\it An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration}, Tech. Report 08-34, CAM UCLA, 2008. |
| [52] | M. Zhu, S. Wright, and T. Chan, {\it Duality-based algorithms for total-variation-regularized image restoration}, Comput. Optim. Appl., 47 (2010), pp. 377-400. · Zbl 1208.90165 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
