×

zbMATH — the first resource for mathematics

Primal-dual block-proximal splitting for a class of non-convex problems. (English) Zbl 1457.90156
Summary: We develop block structure-adapted primal-dual algorithms for non-convex non-smooth optimisation problems, whose objectives can be written as compositions \(G(x)+F(K(x))\) of non-smooth block-separable convex functions \(G\) and \(F\) with a nonlinear Lipschitz-differentiable operator \(K\). Our methods are refinements of the nonlinear primal-dual proximal splitting method for such problems without the block structure, which itself is based on the primal-dual proximal splitting method of Chambolle and Pock for convex problems. We propose individual step length parameters and acceleration rules for each of the primal and dual blocks of the problem. This allows them to convergence faster by adapting to the structure of the problem. For the squared distance of the iterates to a critical point, we show local \(O(1/N), O(1/N^2)\), and linear rates under varying conditions and choices of the step length parameters. Finally, we demonstrate the performance of the methods for the practical inverse problems of diffusion tensor imaging and electrical impedance tomography.
MSC:
90C30 Nonlinear programming
65K10 Numerical optimization and variational techniques
90C48 Programming in abstract spaces
Software:
ARock; Julia
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] P. J. BASSER ANDD. K. JONES,Diffusion-tensor MRI: theory, experimental design and data analysis – a technical review, NMR Biomed., 15 (2002), pp. 456-467.
[2] D. P. BERTSEKAS,Incremental aggregated proximal and augmented Lagrangian algorithms, Preprint on arXiv, 2015.https://arxiv.org/abs/1509.09257
[3] J. BEZANSON, A. EDELMAN, S. KARPINSKI,ANDV. B. SHAH,Julia: a fresh approach to numerical computing, SIAM Rev., 59 (2017), pp. 65-98. · Zbl 1356.68030
[4] P. BIANCHI, W. HACHEM,ANDI. FRANCK,A stochastic coordinate descent primal-dual algorithm and applications, in 2014 IEEE International Workshop on Machine Learning for Signal Processing (MLSP), IEEE Conference Proceedings, Los Alamitos, 2014, 6 pages.
[5] A. CHAMBOLLE,An algorithm for total variation minimization and applications, J. Math. Imaging Vision, 20 (2004), pp. 89-97. · Zbl 1366.94048
[6] A. CHAMBOLLE, M. J. EHRHARDT, P. RICHTÁRIK,ANDC.-B. SCHÖNLIEB,Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications, SIAM J. Optim., 28 (2018), pp. 2783-2808. · Zbl 06951767
[7] A. CHAMBOLLE ANDT. POCK,A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), pp. 120-145. · Zbl 1255.68217
[8] R. CHAN, H. YANG,ANDT. ZENG,A two-stage image segmentation method for blurry images with Poisson or multiplicative gamma noise, SIAM J. Imaging Sci., 7 (2014), pp. 98-127. · Zbl 1297.65066
[9] C. CLASON, S. MAZURENKO,ANDT. VALKONEN,Acceleration and global convergence of a first-order primal-dual method for nonconvex problems, SIAM J. Optim., 29 (2019), pp. 933-963. · Zbl 1414.49037
[10] ,Primal-dual proximal splitting and generalized conjugation in nonsmooth nonconvex optimization, Appl. Math. Optim, (2020).https://doi.org/10.1007/s00245-020-09676-1.
[11] C. CLASON ANDT. VALKONEN,Primal-dual extragradient methods for nonlinear nonsmooth PDEconstrained optimization, SIAM J. Optim., 27 (2017), pp. 1314-1339. · Zbl 1369.49040
[12] P. L. COMBETTES ANDJ. PESQUET,Stochastic forward-backward and primal-dual approximation algorithms with application to online image restoration, in 2016 24th European Signal Processing Conference (EUSIPCO), IEEE Conference Proceedings, Los Alamitos, 2016, pp. 1813-1817.
[13] D. CSIBA, Z. QU,ANDP. RICHTTÁRIK,Stochastic dual coordinate ascent with adaptive probabilities, in Proceedings of the 32nd International Conference on Machine Learning, F. Bach and D. Blei, eds., vol. 37 of Proceedings of Machine Learning Research, PMLR, 2015, pp. 674-683.
[14] D. DAVIS ANDD. DRUSVYATSKIY,Stochastic model-based minimization of weakly convex functions, SIAM J. Optim., 29 (2019), pp. 207-239. · Zbl 1415.65136
[15] O. FERCOQ ANDP. BIANCHI,A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions, SIAM J. Optim., 29 (2019), pp. 100-134. · Zbl 1411.90265
[16] O. FERCOQ ANDP. RICHTÁRIK,Accelerated, parallel, and proximal coordinate descent, SIAM J. Optim., 25 (2015), pp. 1997-2023. · Zbl 1327.65108
[17] P. GETREUER, M. TONG,ANDL. A. VESE,A variational model for the restoration of MR images corrupted by blur and Rician noise, in Advances in Visual Computing, G. Bebis et al., eds., vol. 6938 of Lecture Notes in Computer Science, Springer, Berlin, 2011, pp. 686-698.
[18] J. JAUHIAINEN, P. KUUSELA, A. SEPPÄNEN,ANDT. VALKONEN,Relaxed Gauss-Newton methods with applications to electrical impedance tomography, SIAM J. Imaging Sci., 13 (2020), pp. 1415-1445.
[19] P. KINGSLEY,Introduction to diffusion tensor imaging mathematics: Parts I-III, Concepts Magn. Res. Part A, 28 (2006), pp. 101-179.
[20] A. MARTÍN ANDE. SCHIAVI,Automatic total generalized variation based DTI Rician denoising, Int. Conf. in Image Analysis and Recognition, M. Kamel and A. Campilho, eds., vol. 7950 of Lecture Notes in Computer Science, Springer, Heidelberg, 2013, pp. 581-588.
[21] S. MAZURENKO, J. JAUHIAINEN,ANDT. VALKONEN,Diffusion tensor imaging codes from “primal-dual block-proximal splitting for a class of non-convex problems”. Software on Zenodo, November 2019. doi:10.5281/zenodo.3528137
[22] A. MILZAREK, X. XIAO, S. CEN, Z. WEN,ANDM. ULBRICH,A stochastic semismooth Newton method for nonsmooth nonconvex optimization, SIAM J. Optim., 29 (2019), pp. 2916-2948. · Zbl 1434.90108
[23] Y. NESTEROV,Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), pp. 341-362. · Zbl 1257.90073
[24] D. NISHIMURA,Principles of Magnetic Resonance Imaging, Stanford University, Stanford, 1996.
[25] Z. PENG, Y. XU, M. YAN,ANDW. YIN,ARock: an algorithmic framework for asynchronous parallel coordinate updates, SIAM J. Sci. Comput., 38 (2016), pp. A2851-A2879. · Zbl 1350.49041
[26] M. PILANCI ANDM. J. WAINWRIGHT,Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares, J. Mach. Learn. Res., 17 (2016), Paper No. 53, 38 pages. · Zbl 1360.62400
[27] Z. QU, P. RICHTÁRIK, M. TAKÁ ˇC,ANDO. FERCOQ,SDNA: Stochastic dual newton ascent for empirical risk minimization, in Proceedings of The 33rd International Conference on Machine Learning, M. F. Balcan
[28] P. RICHTÁRIK ANDM. TAKÁ ˇC,Distributed coordinate descent method for learning with big data, J. Mach. Learn. Res., 17 (2016), Paper No. 75, 25 pages.
[29] ,Parallel coordinate descent methods for big data optimization, Math. Program., 156 (2016), pp. 433- 484. · Zbl 1342.90102
[30] R. T. ROCKAFELLAR ANDR. J.-B. WETS,Variational Analysis, Springer, Berlin, 1998.
[31] S. SHALEV-SHWARTZ ANDT. ZHANG,Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization, Math. Program., 155 (2016), pp. 105-145. · Zbl 1342.90103
[32] T. SUZUKI,Stochastic dual coordinate ascent with alternating direction method of multipliers, in Proceedings of the 31st International Conference on Machine Learning, E. P. Xing and T. Jebara, eds., vol. 32 of Proceedings of Machine Learning Research, PMLR, 2014, pp. 736-744.
[33] T. VALKONEN,A primal-dual hybrid gradient method for non-linear operators with applications to MRI, Inverse Problems, 30 (2014), Art. 055012, 45 pages. · Zbl 1310.47081
[34] ,Testing and non-linear preconditioning of the proximal point method, Appl. Math. Optim., (2018). https://doi.org/10.1007/s00245-018-9541-6
[35] ,Block-proximal methods with spatially adapted acceleration, Electron. Trans. Numer. Anal., 51 (2019), pp. 15-49. http://etna.ricam.oeaw.ac.at/vol.51.2019/pp15-49.dir/pp15-49.pdf · Zbl 1420.49034
[36] ,First-order primal-dual methods for nonsmooth nonconvex optimisation, in Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging, K. Chen, C.-B. Schönlieb, X.-C. Tai, and L. Younes, eds., Springer, 2020, in press.
[37] T. VALKONEN, K. BREDIES,ANDF. KNOLL,TGV for diffusion tensors: a comparison of fidelity functions, J. Inverse Ill-Posed Probl., 21 (2013), pp. 355-377. · Zbl 1301.92046
[38] ,Total generalised variation in diffusion tensor imaging, SIAM J. Imaging Sci. 6 (2013), pp. 487-525. · Zbl 1322.94024
[39] T. VALKONEN ANDM. LIEBMANN,GPU-accelerated regularisation of large diffusion tensor volumes, Computing, 95 (2013), pp. S771-S784.
[40] VARIOUS AUTHORS,Teem toolkit, version 1.11.0, 2012.http://teem.sourceforge.net.
[41] P. J. VAUHKONEN, M. VAUHKONEN, T. SAVOLAINEN,ANDJ. P. KAIPIO,Three-dimensional electrical impedance tomography based on the complete electrode model, IEEE Trans. Biomed. Engrg., 46 (1999), pp. 1150-1160.
[42] S. J. WRIGHT,Coordinate descent algorithms, Math. Program., 151 (2015), pp. 3-34. · Zbl 1317.49038
[43] Y. XU ANDW. YIN,Block stochastic gradient iteration for convex and nonconvex optimization, SIAM J. Optim., 25 (2015), pp. 1686-1716. · Zbl 1342.93125
[44] ,A globally convergent algorithm for nonconvex optimization based on block coordinate update, J. Sci. Comput., 72 (2017), pp. 700-734. · Zbl 1378.65126
[45] Y. ZHANG ANDL. XIAO,Stochastic primal-dual coordinate method for regularized empirical risk minimization, J. Mach. Learn. Res., 18 (2017), Paper No. 84, 42 pages. · Zbl 1440.62314
[46] P.
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.