×

zbMATH — the first resource for mathematics

Generalized Peaceman-Rachford splitting method for multiple-block separable convex programming with applications to robust PCA. (English) Zbl 1368.90129
Summary: The Peaceman-Rachford splitting method (PRSM) is an efficient approach for two-block separable convex programming. In this paper we extend this method to the general case where the objective function consists of the sum of multiple convex functions without coupled variables, and present a generalized PRSM. Theoretically, we prove global convergence of the new method and establish the worst-case convergence rate measured by the iteration complexity in the ergodic sense for the new method. Numerically, its efficiency is illustrated by synthetic data about the robust principal component analysis (PCA) model with noisy and incomplete information.

MSC:
90C25 Convex programming
90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Tao, M; Yuan, XM, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21, 57-81, (2011) · Zbl 1218.90115
[2] Peng, Y.G., Ganesh, A., Wright, J., Xu, W.L., Ma, Y.: Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Con. Comput. Vision Patt. Recog. (CVPR), 763-770 (2010)
[3] McLACHLAN, G.: Discriminant analysis and statistical pattern recognition, Wiley-Interscience, (2004) · Zbl 1108.62317
[4] Gabay, D; Mercier, B, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2, 16-40, (1976) · Zbl 0352.65034
[5] Peaceman, DH; Rachford, HH, The numerical solution of parabolic elliptic differential equations, SIAM J. Appl. Math., 3, 28-41, (1955) · Zbl 0067.35801
[6] Lions, PL; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Num. Analy., 16, 964-979, (1979) · Zbl 0426.65050
[7] Han, D; Yuan, XM, Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J. Numer. Anal., 51, 3446-3457, (2013) · Zbl 1285.90033
[8] He, BS; Liu, H; Wang, ZR; Yuan, XM, A strictly contractive peaceman-Rachford splitting method for convex programming, SIAM J. Optim, 24, 1011-1040, (2014) · Zbl 1327.90210
[9] Sun, M., Liu, J.: A proximal Peaceman-Rachford splitting method for compressive sensing, J. Appl. Math. Comput., (2015) (Accepted) · Zbl 1330.90079
[10] Li, XX; Yuan, XM, A proximal strictly contractive peaceman-Rachford splitting method for convex programming with applications to imaging, SIAM J. Imaging Sci., 8, 1332-1365, (2015) · Zbl 1327.90215
[11] Duchi, J; Singer, Y, Efficient online and batch learning using forward backword splitting, J. Mach. Learn. Res., 10, 2899-2934, (2009) · Zbl 1235.62151
[12] Cai, J; Chan, R; Nikolova, M, Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise, Inverse Probl. Imaging, 2, 187-204, (2008) · Zbl 1154.94306
[13] Facchinei, F., Pang, J.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Vols I and II. Springer, Berlin (2003) · Zbl 1062.90002
[14] Hou, L.S., He, H.J., Yang, J.F.: A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA, Comput. Optim. Appl. (2015) (Accepted) · Zbl 1343.90061
[15] CandĂ©s, E; Li, X; Ma, Y; Wright, J, Robust principal component analysis?, J. ACM, 58, 1-37, (2011) · Zbl 1327.62369
[16] Fazel, M., Goodman, J.: Approximations for partially coherent optical imaging systems. Stanford University, Tech. Rep. (1998) · Zbl 1235.62151
[17] He, B.S., Xu, H.K., Yuan, X.M.: On the proximal jacobina decomposition of ALM for multiple-block separable convex minimization problems and its relationship to ADMM, J. Sci. Comput. (2015) (Accepted) · Zbl 1371.65052
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.