
-
Previous Article
Inversion of weighted divergent beam and cone transforms
- IPI Home
- This Issue
-
Next Article
Some remarks on the small electromagnetic inhomogeneities reconstruction problem
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 |
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 [
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. |
show all references
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. |








Parameters | α | σ | ηmin | C | βk | ρ | τ |
Values | 10 | 2 | ||A||2/10 | 100 | 1/k | 1 | 1 |
Parameters | α | σ | ηmin | C | βk | ρ | τ |
Values | 10 | 2 | ||A||2/10 | 100 | 1/k | 1 | 1 |
Parameters | α | σ | ηmin | C |
Values | 10-10n | 2 | ||A||2/5 | 100 |
Parameters | α | σ | ηmin | C |
Values | 10-10n | 2 | ||A||2/5 | 100 |
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 |
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 |
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 |
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 |
[1] |
Leyu Hu, Wenxing Zhang, Xingju Cai, Deren Han. A parallel operator splitting algorithm for solving constrained total-variation retinex. Inverse Problems and Imaging, 2020, 14 (6) : 1135-1156. doi: 10.3934/ipi.2020058 |
[2] |
Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems and Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547 |
[3] |
Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091 |
[4] |
Huan Gao, Yu-Hong Dai, Xiao-Jiao Tong. Barzilai-Borwein-like methods for the extreme eigenvalue problem. Journal of Industrial and Management Optimization, 2015, 11 (3) : 999-1019. doi: 10.3934/jimo.2015.11.999 |
[5] |
Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial and Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181 |
[6] |
Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021028 |
[7] |
Mujibur Rahman Chowdhury, Jun Zhang, Jing Qin, Yifei Lou. Poisson image denoising based on fractional-order total variation. Inverse Problems and Imaging, 2020, 14 (1) : 77-96. doi: 10.3934/ipi.2019064 |
[8] |
Haijuan Hu, Jacques Froment, Baoyan Wang, Xiequan Fan. Spatial-Frequency domain nonlocal total variation for image denoising. Inverse Problems and Imaging, 2020, 14 (6) : 1157-1184. doi: 10.3934/ipi.2020059 |
[9] |
Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems and Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008 |
[10] |
Zhengmeng Jin, Chen Zhou, Michael K. Ng. A coupled total variation model with curvature driven for image colorization. Inverse Problems and Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031 |
[11] |
Sudeb Majee, Subit K. Jain, Rajendra K. Ray, Ananta K. Majee. A fuzzy edge detector driven telegraph total variation model for image despeckling. Inverse Problems and Imaging, 2022, 16 (2) : 367-396. doi: 10.3934/ipi.2021054 |
[12] |
Yuan Shen, Chang Liu, Yannian Zuo, Xingying Zhang. A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022101 |
[13] |
Hai Huyen Dam, Siow Yong Low, Sven Nordholm. Two-level optimization approach with accelerated proximal gradient for objective measures in sparse speech reconstruction. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021131 |
[14] |
Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems and Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 |
[15] |
Xavier Bresson, Tony F. Chan. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems and Imaging, 2008, 2 (4) : 455-484. doi: 10.3934/ipi.2008.2.455 |
[16] |
Ke Chen, Yiqiu Dong, Michael Hintermüller. A nonlinear multigrid solver with line Gauss-Seidel-semismooth-Newton smoother for the Fenchel pre-dual in total variation based image restoration. Inverse Problems and Imaging, 2011, 5 (2) : 323-339. doi: 10.3934/ipi.2011.5.323 |
[17] |
Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems and Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191 |
[18] |
Gang Li, Xiaoqi Yang, Yuying Zhou. Stable strong and total parametrized dualities for DC optimization problems in locally convex spaces. Journal of Industrial and Management Optimization, 2013, 9 (3) : 671-687. doi: 10.3934/jimo.2013.9.671 |
[19] |
Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial and Management Optimization, 2022, 18 (2) : 773-794. doi: 10.3934/jimo.2020178 |
[20] |
Rinaldo M. Colombo, Francesca Monti. Solutions with large total variation to nonconservative hyperbolic systems. Communications on Pure and Applied Analysis, 2010, 9 (1) : 47-60. doi: 10.3934/cpaa.2010.9.47 |
2021 Impact Factor: 1.483
Tools
Metrics
Other articles
by authors
[Back to Top]