## 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.

Original language | English |
---|---|

Article number | 115011 |

Journal | Inverse Problems |

Volume | 32 |

Issue number | 11 |

DOIs | |

Publication status | Published - 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