An Efficient Primal-Dual Hybrid Gradient Algorithm For Total Variation Image Restoration

By Mingqiang Zhu, Tony F. Chan. 2008

569 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/49045e5ba71a98c4f88f3b3824d315912e747808

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging (2011, unknown): “We have observed that replacing the last updating rule in (39) with ¯ x n +1 = x n +1 , which corresponds to considering the standard Arrow-Hurwicz al-gorithm with varying steps as in [34], the same rate of convergence is observed (with even smaller constants, in practice) than using Algorithm (2).”
A Direct Algorithm for 1-D Total Variation Denoising (2013, methodology): “the primal and dual formulations of the problems and use variable stepsize strategies or Nesterov-style accelerations, are quite efficient when applied to TV-based problems [19, 20, 21, 22, 23].”
Stabilizing Adversarial Nets With Prediction Methods (2017, methodology): “One popular solver is the primal-dual hybrid gradient (PDHG) method (Zhu & Chan, 2008; Esser et al., 2009), which has been popularized by Chambolle and Pock (Chambolle & Pock, 2011), and has been successfully applied to a range of machine learning and statistical estimation problems (Goldstein et…”
A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science (2010, methodology): “The saddle point formulation for PDHG applied to TV minimization problems in [58] is based on the observation that u T V = max p∈X p, Du, (3.8) where X = {p ∈ R e : p E * ≤ 1} .”
An introduction to continuous optimization for imaging (2016, methodology): “They have also been used by Bonettini and Ruggiero (2012) to reinterpret a primal–dual scheme of Zhu and Chan (2008) (see Section 5.1) and prove its convergence.”
Randomized First-Order Methods for Saddle Point Optimization (2014, unknown): “1) can be solved effectively by using primal-dual algorithms [8, 2, 5, 23] and Alternating Direction Method of Multipliers (ADMM) methods [4, 12, 6, 19].”
Modern regularization methods for inverse problems (2018, methodology): “The inner variational regularization method is solved via the primal-dual hybrid gradient method (PDHGM), see [373, 307, 171, 113, 115].”
Infimal convolution regularizations with discrete ℓ1-type functionals (2011, methodology): “Sparked by [12, 13, 21, 40, 44], splitting methods which make use of the additive structure of the objective function have become popular recently in image processing.”
An introduction to Total Variation for Image Analysis (2009, methodology): “This suggests the following approach, which consists in performing simultaneously an approximate gradient descent in x and gradient ascent in y: choose x0, y0, τ, σ > 0 two time-steps, and let yn+1 = (I + σ∂F ∗)−1(yn + σAxn) xn+1 = (I + τ∂G)−1(xn − τA∗yn+1) The scheme, as is, is proposed in a paper ”
A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration (2010, methodology): “Some examples are discussed in [26] which uses a variant of the PDHG method [52] and shows it to be a special case of the algorithm (3.”
On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty (2011, unknown): “Zhu and Chan [12] studied a primal-dual formulation and a so-called ‘primal-dual hybrid gradient descent’ (PDHG) algorithm but concentrated on deconvolution.”
Optimal Primal-Dual Methods for a Class of Saddle Point Problems (2013, background): “The study on ﬁrst-order primal-dual method for nonsmooth convex optimization has been mainly motivated by solving total variation based image processing problems (e.g. [45, 9, 37, 6, 4, 13]).”
An algorithm for minimizing the Mumford-Shah functional (2009, methodology): “Our scheme is also related to a more simple primal-dual projected gradient ascend/descend scheme which has been used in [21], but for which convergence has not been proven so far.”
Convergence Analysis of Primal-Dual Algorithms for a Saddle-Point Problem: From Contraction Perspective (2012, methodology): “To close this subsection, we discuss the relationship of the proposed Algorithm 2 with the PDHG method in [25].”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, methodology): “minimization, coordinate minimization, and gradient projection methods have been proposed for its solution [60, 108, 147, 152, 160, 161].”
A Primer on Monotone Operator Methods (2015, unknown): “This setup has been studied in several contexts such as image processing [23,48,133].”
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery (2009, background): “4) in the special case A = I (denoising problem); see [17, 22, 35, 61].”
Image super-resolution: The techniques, applications, and future (2016, methodology): “Unlike the quadratic regularizations, edge information can be better preserved using TV regularization, with the l1 norm to deal with the image information rather than the l2 norm [47,104,105].”
Image restoration: Total variation, wavelet frames, and beyond (2012, methodology): “Recent developments of the duality based method can be found in [14, 15, 16, 17, 18] and the references therein.”