Accelerated bregman operator splitting with backtracking

Yunmei Chen; Xianqi Li; Yuyuan Ouyang; Eduardo Pasiliao

doi:10.3934/ipi.2017048

Article Contents

2017, Volume 11, Issue 6: 1047-1070. Doi: 10.3934/ipi.2017048

This issue Previous Article Some remarks on the small electromagnetic inhomogeneities reconstruction problem Next Article Inversion of weighted divergent beam and cone transforms

Accelerated bregman operator splitting with backtracking

1.
Department of Mathematics, University of Florida, Gainesville, FL 32611, USA
2.
Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, USA
3.
Munitions Directorate, Air Force Research Laboratory, Eglin AFB, FL 32542-9998, USA

* Corresponding author: Xianqi Li
* Corresponding author: Xianqi Li

Received: October 31, 2016

Revised: May 31, 2017

Published: November 2017

The first author is supported by NSF grant DMS-1319050, NSF/DMS 1719932 and AFOSR/Eglin (FA8651-08-D-0108). The second author was partially supported by UFII fellowship and AFRL Mathematical Modeling and Optimization Institute.

Abstract Full Text(HTML) Figure(8) / Table(4) Related Papers Cited by

Abstract

This paper develops two accelerated Bregman Operator Splitting (BOS) algorithms with backtracking for solving regularized large-scale linear inverse problems, where the regularization term may not be smooth. The first algorithm improves the rate of convergence for BOSVS [5] in terms of the smooth component in the objective function by incorporating Nesterov's multi-step acceleration scheme under the assumption that the feasible set is bounded. The second algorithm is capable of dealing with the case where the feasible set is unbounded. Moreover, it allows more aggressive stepsize than that in the first scheme by properly selecting the penalty parameter and jointly updating the acceleration parameter and stepsize. Both algorithms exhibit better practical performance than BOSVS and AADMM [21], while preserve the same accelerated rate of convergence as that for AADMM. The numerical results on total-variation based image reconstruction problems indicate the effectiveness of the proposed algorithms.

Keywords:

Mathematics Subject Classification: Primary: 90C25, 90C52; Secondary: 65Y20, 68W40.

Citation:

Full Text(HTML)

Figure 1. The objective function values and relative error vs. CPU time for first instance

Download: Full-size image PowerPoint slide

Figure 2. The objective function values and relative error vs.CPU time for second instance

Download: Full-size image PowerPoint slide

Figure 3. Sensitivity maps of data1

Download: Full-size image PowerPoint slide

Figure 4. Left: True image; Right: Cartesian mask for data 1

Download: Full-size image PowerPoint slide

Figure 5. Comparison of 400 iterations of BOSVS, TVAL3, ALADMML, and ABOSVS-Ⅱ in partially parallel image reconstruction (Top) and their differences with true image (Bottom) using data1. From left to right: BOSVS, TVAL3, ALADMML, and ABOSVS-Ⅱ

Download: Full-size image PowerPoint slide

Figure 6. Sensitivity maps of data2

Download: Full-size image PowerPoint slide

Figure 7. Left: True image; Right: Cartesian mask for data 2

Download: Full-size image PowerPoint slide

Figure 8. Comparison of 400 iterations of BOSVS, TVAL3, ALADMML, and ABOSVS-Ⅱ in partially parallel image reconstruction (Top) and their differences with true image (Bottom) using data2. From left to right: BOSVS, TVAL3, ALADMML, and ABOSVS-Ⅱ.

Download: Full-size image PowerPoint slide

Table 1. Parameter settings for ABOSVS-I and ABOSVS-Ⅱ in (4.1). Note that $\rho$ and $\tau$ are only used in the first instance

Parameters α σ η_min C β_k ρ τ

Values 10 2 ||A||²/10 100 1/k 1 1

| Show Table

DownLoad: CSV

Table 2. Parameter settings for ABOSVS-Ⅱ in 4.2

Parameters α σ η_min C

Values 10^-10n 2 ||A||²/5 100

| Show Table

DownLoad: CSV

Table 3. Comparison of objective function value, relative error, and CPU time in seconds using data1

Algorithms Objective value Relative error CPU

BOSVS 15.46841 0.0596 2528.0

TVAL3 56.7263 0.050 228.6

ALADMML 15.46810 0.0499 66.5

ABOSVS-Ⅱ 15.44535 0.0479 49.7

| Show Table

DownLoad: CSV

Table 4. Comparison of objective function value, relative error, and CPU time in seconds using data2

Algorithms Objective value Relative error CPU

BOSVS 5007e+2 0.0646 7448.4

TVAL3 1704e+3 0.050 681.2

ALADMML 5.006e+2 0.0499 180.0

ABOSVS-Ⅱ 4.970e+2 0.0479 144.7

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Beck and M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Transactions on Image Processing, 18 (2009), 2419-2434. doi: 10.1109/TIP.2009.2028250.
[2]	K. Block, M. Uecker and J. Frahm, Undersampled radial MRI with multiple coils. Iterative image reconstruction using a total variation constraint, Magnetic Resonance in Medicine, 57 (2007), 1086-1098. doi: 10.1002/mrm.21236.
[3]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine Learning, 3 (2011), 1-122. doi: 10.1561/2200000016.
[4]	Y. Chen, W. Hager, F. Huang, D. Phan, X. Ye and W. Yin, Fast algorithms for image reconstruction with application to partially parallel MR imaging, SIAM Journal on Imaging Sciences, 5 (2012), 90-118. doi: 10.1137/100792688.
[5]	Y. Chen, W. Hager, M. Yashtini and X. Ye, Bregman operator splitting with variable stepsize for total variation image reconstruction, Computational Optimization and Applications, 54 (2013), 317-342. doi: 10.1007/s10589-012-9519-2.
[6]	W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, Journal of Scientific Computing, 66 (2012), 1-28. doi: 10.1007/s10915-015-0048-x.
[7]	D. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[8]	D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers & Mathematics with Applications, 2 (1976), 17-40. doi: 10.1016/0898-1221(76)90003-1.
[9]	R. Glowinski and A. Marroco, 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 non linéaires, Revue française d'automatique, informatique, recherche opérationnelle. Analyse numérique, 9 (1975), 41-76.
[10]	D. Goldfarb, S. Ma and K. Scheinberg, Fast multiple-splitting algorithms for convex optimization, SIAM Journal on Optimization, 22 (2012), 533-556. doi: 10.1137/090780705.
[11]	T. Goldstein, B. O'Donoghue, S. Setzer and R. Baraniuk, Fast alternating direction optimization methods, SIAM Journal on Imaging Sciences, 7 (2014), 1588-1623. doi: 10.1137/120896219.
[12]	T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343. doi: 10.1137/080725891.
[13]	W. Hager, C. Ngo, M. Yashtini and H. Zhang, An alternating direction approximate Newton algorithm for ill-conditioned inverse problems with application to parallel MRI, Name of the Journal, 3 (2015), 139-162. doi: 10.1007/s40305-015-0078-y.
[14]	W. Hager, M. Yashtini and H. Zhang, An $\backslash$mathcalO(1/k) convergence rate for the variable stepsize Bregman operator splitting algorithm, SIAM Journal on Numerical Analysis, 54 (2016), 1535-1556. doi: 10.1137/15100401X.
[15]	M. Hong and Z. Luo, On the linear convergence of the alternating direction method of multipliers, Mathematical Programming, 162 (2017), 165-199, arXiv:1208.3922. doi: 10.1007/s10107-016-1034-2.
[16]	C. Li, W. Yin, H. Jiang and Y. Zhang, An efficient augmented Lagrangian method with applications to total variation minimization, Computational Optimization and Applications, 56 (2013), 507-530. doi: 10.1007/s10589-013-9576-1.
[17]	Q. Liu, J. Luo, S. Wang M. Xiao and M. Ye, An augmented Lagrangian multi-scale dictionary learning algorithm EURASIP Journal on Advances in Signal Processing, 2011 (2011), p58. doi: 10.1186/1687-6180-2011-58.
[18]	M. Lustig, D. Donoho and J. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine, 58 (2007), 1182-1195. doi: 10.1002/mrm.21391.
[19]	R. Monteiro and B. Svaiter, Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers, SIAM Journal on Optimization, 23 (2013), 475-507. doi: 10.1137/110849468.
[20]	Y. Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming, 103 (2005), 127-152. doi: 10.1007/s10107-004-0552-5.
[21]	Y. Ouyang, Y. Chen, G. Lan and E. Pasiliao, An accelerated linearized alternating direction method of multipliers, SIAM Journal on Imaging Sciences, 8 (2015), 644-681. doi: 10.1137/14095697X.
[22]	K. Pruessmann, M. Weiger, P. Börnert and P. Boesiger, Advances in sensitivity encoding with arbitrary k-space trajectories, Magnetic Resonance in Medicine, 46 (2001), 638-651.
[23]	K. Scheinberg, D. Goldfarb and X. Bai, Fast first-order methods for composite convex optimization with backtracking, Foundations of Computational Mathematics, 14 (2014), 389-417. doi: 10.1007/s10208-014-9189-9.
[24]	L. Shepp and B. Logan, The Fourier reconstruction of a head section, IEEE Transactions on Nuclear Science, 21 (1974), 21-43. doi: 10.1109/TNS.1974.6499235.
[25]	Y. Wang, J. Yang, W. Yin and Y. Zhang A new alternating minimization algorithm for total variation image reconstruction, A new alternating minimization algorithm for total variation image reconstruction, SIAM Journal on Imaging Sciences, 1 (2008), 248-272. doi: 10.1137/080724265.
[26]	B. Wohlberg, Efficient Algorithms for Convolutional Sparse Representations, IEEE Transactions on Image Processing, 25 (2016), 301-315. doi: 10.1109/TIP.2015.2495260.
[27]	J. Yang, Y. Zhang and W. Yin, A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data, IEEE Journal of Selected Topics in Signal Processing, 4 (2010), 288-297.
[28]	X. Ye, Y. Chen and F. Huang, Computational acceleration for MR image reconstruction in partially parallel imaging, IEEE Transactions on Medical Imaging, 30 (2011), 1055-1063.
[29]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM Journal on Imaging Sciences, 3 (2010), 253-276. doi: 10.1137/090746379.
[30]	X. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on Bregman iteration, Journal of Scientific Computing, 46 (2011), 20-46. doi: 10.1007/s10915-010-9408-8.
[31]	M. Zhu and T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, UCLA CAM Report, (2008), 8-34.
[32]	M. Zhu, S. Wright and T. Chan, Duality-based algorithms for total-variation-regularized image restoration, Computational Optimization and Applications, 47 (2010), 377-400. doi: 10.1007/s10589-008-9225-2.