Linearized primal-dual methods for linear inverse problems with total variation regularization and finite element discretization

Wenyi Tian, Xiaoming YUAN*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

9 Citations (Scopus)


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.

Original languageEnglish
Article number115011
JournalInverse Problems
Issue number11
Publication statusPublished - 3 Oct 2016

Scopus Subject Areas

  • Theoretical Computer Science
  • Signal Processing
  • Mathematical Physics
  • Computer Science Applications
  • Applied Mathematics

User-Defined Keywords

  • convergence rate
  • finite element
  • linear inverse problem
  • numerical optimization
  • primal-dual method
  • saddle-point problem
  • total variation


Dive into the research topics of 'Linearized primal-dual methods for linear inverse problems with total variation regularization and finite element discretization'. Together they form a unique fingerprint.

Cite this