A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA

• DOI: 10.1007/s10589-015-9770-4
• Publication Date: 2015-06-24T11:02:46Z
• Authors: Liusheng Hou; Hongjin He; Junfeng Yang
• Keywords: Augmented Lagrangian method; Rank (graph theory)

We consider a multiple-block separable convex programming problem, where the objective function is the sum of m individual convex functions without overlapping variables, and the constraints are linear, aside from side constraints. Based on the combination of the classical Gauss---Seidel and the Jacobian decompositions of the augmented Lagrangian function, we propose a partially parallel splitting method, which differs from existing augmented Lagrangian based splitting methods in the sense that such an approach simplifies the iterative scheme significantly by removing the potentially expensive correction step. Furthermore, a relaxation step, whose computational cost is negligible, can be incorporated into the proposed method to improve its practical performance. Theoretically, we establish global convergence of the new method in the framework of proximal point algorithm and worst-case nonasymptotic $${\mathcal {O}}(1/t)$$O(1/t) convergence rate results in both ergodic and nonergodic senses, where t counts the iteration. The efficiency of the proposed method is further demonstrated through numerical results on robust PCA, i.e., factorizing from incomplete information of an unknown matrix into its low-rank and sparse components, with both synthetic and real data of extracting the background from a corrupted surveillance video.