A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration

被引:272
作者
Zhang, Xiaoqun [1 ]
Burger, Martin [2 ]
Osher, Stanley [3 ]
机构
[1] Shanghai Jiao Tong Univ, Dept Math, Shanghai 200240, Peoples R China
[2] Univ Munster, Inst Computat & Appl Math, D-48163 Munster, Germany
[3] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 USA
关键词
Saddle point; Bregman iteration; l(1) minimization; Inexact Uzawa methods; Proximal point iteration; THRESHOLDING ALGORITHM; MINIMIZATION; L(1)-MINIMIZATION; RECONSTRUCTION; DECOMPOSITION;
D O I
10.1007/s10915-010-9408-8
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 a"" (1) basis pursuit, TV-L (2) 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.
引用
收藏
页码:20 / 46
页数:27
相关论文
共 52 条
[1]  
[Anonymous], 1958, Stanford Mathematical Studies in the Social Sciences
[2]  
[Anonymous], 0906 UCLA CAM
[3]  
[Anonymous], 2008, 0834 CAM UCLA
[4]  
[Anonymous], 1983, STUDIES MATH ITS APP
[5]  
[Anonymous], 1989, SIAM STUDIES APPL MA
[6]  
Avinash C. K., 2001, PRINCIPLES COMPUTERI
[7]   A FAST ITERATIVE SHRINKAGE-THRESHOLDING ALGORITHM WITH APPLICATION TO WAVELET-BASED IMAGE DEBLURRING [J].
Beck, Amir ;
Teboulle, Marc .
2009 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOLS 1- 8, PROCEEDINGS, 2009, :693-+
[8]  
Becker S., 2009, NESTA FAST ACCURATE
[9]  
Borghi A., 2008, 0864 CAM UCLA
[10]   Analysis of the inexact Uzawa algorithm for saddle point problems [J].
Bramble, JH ;
Pasciak, JE ;
Vassilev, AT .
SIAM JOURNAL ON NUMERICAL ANALYSIS, 1997, 34 (03) :1072-1092