Fast Nonoverlapping Block Jacobi Method for the Dual Rudin-Osher-Fatemi Model

Abstract

We consider nonoverlapping domain decomposition methods for the Rudin-Osher-Fatemi~(ROF) model, which is one of the standard models in mathematical image processing. The image domain is partitioned into rectangular subdomains and local problems in subdomains are solved in parallel. Local problems can adopt existing state-of-the-art solvers for the ROF model. We show that the nonoverlapping relaxed block Jacobi method for a dual formulation of the ROF model has the O(1/n) convergence rate of the energy functional, where n is the number of iterations. Moreover, by exploiting the forward-backward splitting structure of the method, we propose an accelerated version whose convergence rate is O(1/n2). The proposed method converges faster than existing domain decomposition methods both theoretically and practically, while the main computational cost of each iteration remains the same. We also provide the dependence of the convergence rates of the block Jacobi methods on the image size and the number of subdomains. Numerical results for comparisons with existing methods are presented.