A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration

By Xiaoqun Zhang, Martin Burger, Stanley J. Osher. Journal of Scientific Computing, 2010

450 citations recorded by the source corpus.

In this paper, we propose a unified primal-dual algorithm framework for two classes of problems that arise from various signal and image processing applications. We also show the connections to existing methods, in particular Bregman iteration (Osher et al., Multiscale Model. Simul. 4(2):460–489, 2005) based methods, such as linearized Bregman (Osher et al., Commun. Math. Sci. 8(1):93–111, 2010; Cai et al., SIAM J. Imag. Sci. 2(1):226–252, 2009, CAM Report 09-28, UCLA, March 2009; Yin, CAAM Report, Rice University, 2009) and split Bregman (Goldstein and Osher, SIAM J. Imag. Sci., 2, 2009). The convergence of the general algorithm framework is proved under mild assumptions. The applications to ℓ1 basis pursuit, TV−L2 minimization and matrix completion are demonstrated. Finally, the numerical examples show the algorithms proposed are easy to implement, efficient, stable and flexible enough to cover a wide variety of applications.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/9835c6694c9151f2258033e1b2a2321062e67cd7

How researchers see this paper

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

In Computational Mechanics

In Computational Theory and Mathematics

In Mathematical Physics

Citations in the corpus

Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, background): “…the primal and dual problems (63) and (66) jointly, Chambolle and Pock [55] proposed the following algorithms (without relaxation), see also Esser et al. [56] and Zhang et al. [57]: Chambolle–Pock iteration, form I, for (63) and (66) Chambolle–Pock iteration, form II, for (63) and (66): for 𝑖 = 0…”
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers (2016, methodology): “The proof steps are similar to the existing ADM convergence theory in [23,37] but are adapted to Algorithm 2.”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, unknown): “More choices of Pi have also been discussed in [33, 8].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, methodology): “Remarkably, the convergence rate of MISO is linear for minimizing strongly convex composite objective functions, a property shared with two other incremental algorithms for smooth and composite convex optimization: the stochastic average gradient method (SAG) of Schmidt, Le Roux, and Bach [50] and t”
On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty (2011, unknown): “Recently an explicit algorithm was proposed in [15, equation 5.11] with proven convergence.”
Seismic data restoration via data-driven tight frame (2014, methodology): “In this paper, we apply another efficient method, the split inexact Uzawa method proposed in Zhang et al. (2011), which can be viewed as a generalization of the ADMM.”
On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers (2015, methodology): “As in [8], with the attempt to treat the original ADM in [5] and the split inexact Uzawa method in [9, 10] uniformly, we study the following ADM scheme for (1.”
A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration (2013, methodology): “The explicit SIU method proposed in the literature [35] can be described as ⎪⎨⎪⎩ xk+1 = xk − δA (Axk − b) − δνB (Bxk − dk + vk), (4.”
Stochastic Alternating Direction Method of Multipliers (2013, methodology): “Besides that, many variations of this classical method have been recently developed, such as linearized (Goldfarb et al., 2010; Zhang et al., 2011; Yang & Yuan, 2012), accelerated (Goldfarb et al., 2010) and online (Wang & Banerjee, 2012) ADMM.”
Diagonal preconditioning for first order primal-dual algorithms in convex optimization (2011, methodology): “It is easy to check, that the variational inequality (5) now takes the form of a proximal point algorithm [10, 14, 16].”
A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science (2010, methodology): “In this paper we show that we can make a small modification to the PDHG algorithm, which has little effect on its performance, but that allows the modified algorithm to be interpreted as a special case of a split inexact Uzawa method that is analyzed and shown to converge in [56].”
Asynchronous Distributed ADMM for Consensus Optimization (2014, methodology): “The subproblem in each worker is solved by the inexact ADMM algorithm (Zhang et al., 2011).”
Hankel Matrix Rank Minimization with Applications to System Identification and Realization (2013, background): “1The main motivation of introducing the proximal terms in [25] is to weaken the imposed convergence conditions rather than for the sake of cancelation, as was more recently explained in [57].”
An introduction to continuous optimization for imaging (2016, background): “Of course, the reader expert in these approaches Optimization for imaging 235 will see right away that it leads to exactly the same computations as those we would perform for an ADMM implementation (Esser 2009, Zhang et al. 2011, Zhang et al. 2010, Getreuer 2012).”