Local linear convergence analysis of Primal–Dual splitting methods

References

• Rockafellar RT . Convex analysis. Vol. 28. Princeton University Press; 1997.
   Google Scholar
• Chambolle A , Pock T . A first-order primal-dual algorithm for convex problems with applications to imaging. J Math Imaging Vision. 2011;40(1):120–145.
   Web of Science ®Google Scholar
• Briceno-Arias LM , Combettes PL . A monotone+ skew splitting model for composite monotone inclusions in duality. SIAM J Optim. 2011;21(4):1230–1250.
   Web of Science ®Google Scholar
• Vũ BC . A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv Comput Math. 2013;38(3):667–681.
   Web of Science ®Google Scholar
• Combettes PL , Pesquet JC . Primal--Dual splitting algorithm for solving inclusions with mixtures of composite, lipschitzian, and parallel-sum type monotone operators. Set-Valued Variational Anal. 2012;20(2):307–330.
   Web of Science ®Google Scholar
• He B , Yuan X . Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J Imaging Sci. 2012;5(1):119–149.
   Web of Science ®Google Scholar
• Condat L . A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J Optim Theory Appl. 2013;158(2):460–479.
   Web of Science ®Google Scholar
• Chen P , Huang J , Zhang X . A primal-dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Probl. 2013;29(2):025011.
   Web of Science ®Google Scholar
• Arrow K-J , Hurwicz L , Uzawa H , et al . Studies in linear and non-linear programming. Stanford mathematical studies in the social sciences; 1959.
   Google Scholar
• Combettes PL , Vũ BC . Variable metric Forward-Backward splitting with applications to monotone inclusions in duality. Optimization. 2014;63(9):1289–1318.
   Web of Science ®Google Scholar
• Tseng P . A modified Forward--Backward splitting method for maximal monotone mappings. SIAM J Control Optim. 2000;38(2):431–446.
   Web of Science ®Google Scholar
• Lions PL , Mercier B . Splitting algorithms for the sum of two nonlinear operators. SIAM J Numer Anal. 1979;16(6):964–979.
   Web of Science ®Google Scholar
• Douglas J , Rachford HH . On the numerical solution of heat conduction problems in two and three space variables. Trans Amer Math Soc. 1956;82(2):421–439.
   Google Scholar
• Liang J , Fadili J , Peyré G . Activity identification and local linear convergence of Forward-Backward-type methods. SIAM J Optim. 2017;27(1):408–437.
   Web of Science ®Google Scholar
• Liang J , Fadili J , Peyré G . Local convergence properties of Douglas-Rachford and alternating direction method of multipliers. J Optim Theory Appl. 2017;172(3):874–913.
   Web of Science ®Google Scholar
• Davis D . Convergence rate analysis of Primal--Dual splitting schemes. SIAM J Optim. 2015;25(3):1912–1943.
   Web of Science ®Google Scholar
• Liang J , Fadili J , Peyré G . Convergence rates with inexact non-expansive operators. Math Program. 2016 Sep;159(1):403–434.
   Web of Science ®Google Scholar
• Boţ RI , Hendrich A . Convergence analysis for a Primal-dual monotone + skew splitting algorithm with applications to total variation minimization. Technical Report, arXiv:1211.1706, 2012.
   Google Scholar
• Boţ RI , Csetnek ER , Heinrich A , et al . On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems. Math Program. 2015;150(2):251–279.
   Web of Science ®Google Scholar
• Chambolle A , Pock T . On the ergodic convergence rates of a first-order Primal--Dual algorithm. Math Program. 2016;159(1--2):253–287.
   Google Scholar
• Liang J , Fadili J , Peyré G , et al . Activity identification and local linear convergence of Douglas-Rachford/ADMM under partial smoothness. In: International Conference on Scale Space and Variational Methods in Computer Vision. Cham: Springer; 2015. p. 642–653.
   Google Scholar
• Bredies K , Lorenz DA . Linear convergence of iterative soft-thresholding. J Fourier Anal Appl. 2008;14(5–6):813–837.
   Web of Science ®Google Scholar
• Hale E , Yin W , Zhang Y . Fixed-point continuation for l1 -minimization: Methodology and convergence. SIAM J Optim. 2008;19(3):1107–1130.
   Web of Science ®Google Scholar
• Agarwal A , Negahban S , Wainwright MJ . Fast global convergence of gradient methods for high-dimensional statistical recovery. Ann Stat. 2012;40(5):2452–2482.
   Web of Science ®Google Scholar
• Hou K , Zhou Z , So AM-C , et al . On the linear convergence of the proximal gradient method for trace norm regularization. In: Burges CJC , Bottou L , Welling M , et al. , editors. Advances in neural information processing systems 26. Curran Associates; 2013. p. 710–718.
   Google Scholar
• Tao S , Boley D , Zhang S . Local linear convergence of ISTA and FISTA on the lasso problem. SIAM J Optim. 2016;26(1):313–336.
   Web of Science ®Google Scholar
• Demanet L , Zhang X . Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit. Math Comput. 2016;85(297):209–238.
   Web of Science ®Google Scholar
• Boley Daniel . Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs. SIAM J Optim. 2013;23(4):2183–2207.
   Web of Science ®Google Scholar
• Bauschke H , Cruz JYB , Nghia TA , et al . The rate of linear convergence of the Douglas–Rachford algorithm for subspaces is the cosine of the Friedrichs angle. J Approx Theo. 2014;185:63–79.
   Web of Science ®Google Scholar
• Liang J , Fadili J , Peyré G . Local linear convergence of Forward--Backward under partial smoothness. In: Ghahramani Z , Welling M , Cortes C , et al. , editors. Advances in neural information processing systems 27. Curran Associates; 2014. p. 1970–1978.
   Google Scholar
• Sun T , Barrio R , Jiang H , et al . Local linear convergence of a primal-dual algorithm for the augmented convex models. J Sci Comput. 2016;69(3):1301–1315.
   Web of Science ®Google Scholar
• Moreau JJ . Proximité et dualité dans un espace hilbertien. Bull Soc Math France. 1965;93:273–299.
   Google Scholar
• Bauschke HH , Combettes PL . Convex analysis and monotone operator theory in Hilbert spaces. New York (NY): Springer; 2011.
   Google Scholar
• Combettes PL , Yamada I . Compositions and convex combinations of averaged nonexpansive operators. J Math Anal Appl. 2015;425(1):55–70.
   Web of Science ®Google Scholar
• Ogura N , Yamada I . Non-strictly convex minimization over the fixed point set of an asymptotically shrinking non-expansive mapping. Numer Funct Anal Optim. 2002;23:113–137.
   Web of Science ®Google Scholar
• Bauschke HH , Bello Cruz JY , Nghia TTA , et al . Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas--Rachford methods for two subspaces. Numer Alg. 2016;73(1):33–76.
   Web of Science ®Google Scholar
• Lewis AS . Active sets, nonsmoothness, and sensitivity. SIAM J Optim. 2003;13(3):702–725.
   Web of Science ®Google Scholar
• Wright SJ . Identifiable surfaces in constrained optimization. SIAM J Control Optim. 1993;31(4):1063–1079.
   Web of Science ®Google Scholar
• Combettes PL , Condat L , Pesquet J-C , et al . A Forward--Backward view of some primal-dual optimization methods in image recovery. In: 2014 IEEE International Conference on Image Processing (ICIP). Paris: IEEE; 2014. p. 4141–4145.
   Google Scholar
• Briceño-Arias LM , Davis D . Forward--Backward-half forward algorithm with non self-adjoint linear operators for solving monotone inclusions, preprint arXiv:1703.03436, 2017.
   Google Scholar
• Rockafellar RT , Wets R . Variational analysis. Vol. 317. Berlin Heidelberg: Springer Verlag; 1998.
   Google Scholar
• Hare WL , Lewis AS . Identifying active constraints via partial smoothness and prox-regularity. J Convex Anal. 2004;11(2):251–266.
   Web of Science ®Google Scholar
• Silvester JR . Determinants of block matrices. Math Gazette. 2000;84(501):460–467.
   Google Scholar
• Beck A , Teboulle M . A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci. 2009;2(1):183–202.
   Web of Science ®Google Scholar
• Vaiter S , Deledalle C , Fadili J , et al . The degrees of freedom of partly smooth regularizers. Ann Inst Stat Math. 2017;69(4):791–832.
   Web of Science ®Google Scholar
• Esser E , Zhang X , Chan TF . A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J Imaging Sci. 2010;3(4):1015–1046.
   Web of Science ®Google Scholar
• Chavel I . Riemannian geometry: a modern introduction. Vol. 98. Cambridge: Cambridge University Press; 2006.
   Google Scholar
• Miller SA , Malick J . Newton methods for nonsmooth convex minimization: connections among-lagrangian, riemannian newton and SQP methods. Math program. 2005;104(2–3):609–633.
   Web of Science ®Google Scholar
• Absil P-A , Mahony R , Trumpf J . An extrinsic look at the Riemannian Hessian. In: Nielsen F , Barbaresco F , editors. Geometric science of information. Berlin, Heidelberg: Springer; 2013. p. 361–368.
   Google Scholar
• Lee JM . Smooth manifolds. New York (NY): Springer; 2003.
   Google Scholar