Linearized primal-dual methods for linear inverse problems with total variation regularization and finite element discretization. (3rd October 2016)

• Record Type: Journal Article
• Authors: Tian, Wenyi; Yuan, Xiaoming
• Is Part Of: Inverse problems. Volume 32:Number 11(2016:Nov.)
• Publication Date: 2016-10-03
• Subjects: linear inverse problem -- numerical optimization -- saddle-point problem -- primal-dual method -- total variation -- finite element -- convergence rate; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/0266-5611/32/11/115011
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: Linear inverse problems with total variation regularization can be reformulated as saddle-point problems; the primal and dual variables of such a saddle-point reformulation can be discretized in piecewise affine and constant finite element spaces, respectively. Thus, the well-developed primal-dual approach (a.k.a. the inexact Uzawa method) is conceptually applicable to such a regularized and discretized model. When the primal-dual approach is applied, the resulting subproblems may be highly nontrivial and it is necessary to discuss how to tackle them and thus make the primal-dual approach implementable. In this paper, we suggest linearizing the data-fidelity quadratic term of the hard subproblems so as to obtain easier ones. A linearized primal-dual method is thus proposed. Inspired by the fact that the linearized primal-dual method can be explained as an application of the proximal point algorithm, a relaxed version of the linearized primal-dual method, which can often accelerate the convergence numerically with the same order of computation, is also proposed. The global convergence and worst-case convergence rate measured by the iteration complexity are established for the new algorithms. Their efficiency is verified by some numerical results.