A Partial Splitting Augmented Lagrangian Method for Low Patch-Rank Image Decomposition

Following the recent work Schaeffer and Osher (SIAM J Imaging Sci 6:226–262, 2013), the low patch-rank interpretation for the oscillating patterns of an image validates the application of matrix-rank optimization to image decomposition. Therein, the problem was mathematically modeled as a separable convex programming with three-block (a total variation semi-norm for regularizing the cartoon, a low-rank constraint for extracting the texture, and a data fidelity term for approximating the target image), and was algorithmically handled by the split Bregman method with inner Gauss-Seidel sweep loops. In this paper, we develop an alternating direction method of multipliers (ADMM) based prediction–correction method for solving the low patch-rank model with all resulting subproblems admitting closed-form solutions. As a surrogate of the direct extension of ADMM, which was recently proved to be not necessarily convergent, the new method is globally convergent under some mild conditions. Numerical simulations are conducted, which demonstrate the promising performance of the new method.