A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science
A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science
复制标题
DOI：
10.1137/09076934x
复制
发表时间：
2010-01-01
影响因子：
2.1
通讯作者：
Chan, Tony F.
中科院分区：
文献类型：
--
作者：
Esser, Ernie;Zhang, Xiaoqun;Chan, Tony F.
我们将Zhu和Chan在[An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration，CAM Report 08-34，UCLA，洛杉矶，CA，2008]中提出的原始-对偶混合梯度（PDHG）算法推广到更广泛的一类凸优化问题。此外，我们还调查了几种密切相关的方法，并解释了与PDHG的联系。我们指出收敛结果的修改版本的PDHG，具有类似的良好的经验收敛速度的总变差（TV）最小化问题。我们还证明了收敛结果PDHG适用于电视去噪的PDHG步长参数的一些限制。我们将展示如何解释这个特殊的情况下，作为一个投影平均梯度法适用于双功能。我们讨论了这些方法可以收敛的参数范围。我们还提出了一些数值比较，这些算法适用于电视去噪，电视去模糊，约束l（1）最小化问题。
We generalize the primal-dual hybrid gradient (PDHG) algorithm proposed by Zhu and Chan in [An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, CAM Report 08-34, UCLA, Los Angeles, CA, 2008] to a broader class of convex optimization problems. In addition, we survey several closely related methods and explain the connections to PDHG. We point out convergence results for a modified version of PDHG that has a similarly good empirical convergence rate for total variation (TV) minimization problems. We also prove a convergence result for PDHG applied to TV denoising with some restrictions on the PDHG step size parameters. We show how to interpret this special case as a projected averaged gradient method applied to the dual functional. We discuss the range of parameters for which these methods can be shown to converge. We also present some numerical comparisons of these algorithms applied to TV denoising, TV deblurring, and constrained l(1) minimization problems.