A Uniform Preconditioner for a Newton Algorithm for Total Variation Minimization and Minimum-Surface Problems

Abstract

Solution methods for the nonlinear PDE of the Rudin–Osher–Fatemi (ROF) and minimum-surface models are fundamental for many modern applications. Many efficient algorithms have been proposed. First-order methods are common. They are popular due to their simplicity and easy implementation. Some second-order Newton-type iterative methods have been proposed, such as Chan–Golub–Mulet method. In this paper, we propose a new Newton–Krylov solver for primal-dual finite element discretization of the ROF model and the minimum-surface model. The method is so simple that we just need to use some diagonal preconditioners during the iterations. Theoretically, the proposed preconditioners are further proved to be robust and optimal with respect to the mesh size, the penalization parameter, the regularization parameter, and the iterative step; essentially, it is a parameter-independent preconditioner. We first discretize the primal-dual system by using mixed finite element methods and then linearize the discrete system by Newton’s method. Exploiting the well-posedness of the linearized problem on appropriate Sobolev spaces equipped with proper norms, we propose block diagonal preconditioners for the corresponding system solved with the minimum residual method. Numerical results are presented to support the theoretical results.