凸可分离优化问题的原始对偶不动点算法及其应用
|
摘要
在基于有界变差的图像处理领域，很多问题可以表示为求解两个可分离的凸函数的最小化问题，近年来该问题得到了广泛研究与应用.本文从原始对偶不动点算法的观点提出一系列的算法求解两个可分离的凸函数的最小化问题，问题中一个函数为凸函数和线性变换的复合，一个函数的梯度是Lipschitz连续的.所提出的算法具体包括基于邻近算子的原始对偶不动点算法（PDFP~2O）、凸集上的基于邻近算子的原始对偶不动点算法（PDFP~2O_C）、基于邻近算子和预处理算子的原始对偶不动点算法（PDFP~3O）.
在基于邻近算子的前向后向算子分裂算法（PFBS）和基于邻近算子的不动点算法（FP~2O）的基础上，首先从直观上得到PDFP~2O.然后利用一阶优化条件，通过引入对偶变量，利用邻近算子与次梯度的等价关系，通过两步额外的迭代，可以将提出的算法表示成算子的不动点迭代形式，并因此得到PDFP~2O的拓展版本PDFP~2Oκ.利用邻近算子的强非扩张性，在特殊构造的范数的帮助下，证明了PDFP~2Oκ的收敛性.在稍强的条件下，进一步给出了算法PDFP~2Oκ的收敛速度.接下来，通过等价变形，进一步解释了算法PDFP~2O，并给出了与其他已有算法的联系和区别.最后通过关于图像放大、CT重构、并行核磁共振成像的数值实验说明了算法的有效性.总体来说，PDFP~2O的性能和当前顶尖的算法的性能是可比较的，而PDFP~2O的参数的选择相对容易，这在求解具体的实际问题中是很有意义的.
对于很多实际问题，根据不同的物理背景，解的取值都有一定的限制.所以，进一步考虑求解带凸集约束的可分离凸优化问题.通过将凸集的约束表示成示性函数而加入目标函数中的技巧，适当重新组合，可直接利用PDFP~2O求解，利用函数的可分离性，得到PDFP~2O_C.因为PDFP~2O_C本质上就是利用PDFP~2O求解与原问题等价的无约束优化问题，根据PDFP~2O的证明结果，可以方便的得到PDFP~2O_C的收敛性以及收敛速度.在解位于凸集内部的假设条件下，利用示性函数的邻近算子为投影算子，类似于PDFP~2O的推导，通过算子的不动点迭代得到求解解位于凸集内部的可分离凸优化问题的基于邻近算子的原始对偶不动点算法（PDFP~2O_C0）.利用投影算子也是强非扩张算子的性质，并利用PDFP~2O的证明结果，得到PDFP~2O_C0的收敛性以及收敛速度.一般来说，算法PDFP~2O_C具有很好的通用性，算法PDFP~2O_C0只适用于解位于凸集内部的情形，但其迭代形式更简单、直观.最后通过CT重构和并行核磁共振成像说明了算法PDFP~2O_C和PDFP~2O_C0的有效性.
从收敛速度的估计中，以及CT重构的数值实验结果中，可以看出PDFP~2O的收敛速度和相应矩阵的条件数有关，当其中一个矩阵的条件数变差时，PDFP~2O的收敛速度会变慢.所以，进一步考虑利用预处理算子来加速，提出PDFP~3O.类似于PDFP~2O的推导，通过额外引入两个预处理算子可以得到PDFP~3O.通过引入另一个特殊构造的范数，类似于PDFP~2O的证明，可以证明PDFP~3O的收敛性与收敛速度.并进一步将PDFP~3O与精确Uzawa、不精确Uzawa算法和非线性不精确Uzawa算法比较，并利用不动点算法框架导出这些算法.最后，通过第二类椭圆变分不等式中的两个实例，说明当问题条件数较差时，PDFP~3O的确优于PDFP~2O.在简化的摩擦问题中，根据一阶优化条件，将退化的问题转化为非退化的问题；根据新问题中的迭代矩阵的内蕴性质，给出了选择预处理矩阵的方法.在管中的粘塑性流体问题中，尝试采用共轭梯度法获得预处理矩阵的效果.
In recent years, minimization of a sum of two convex functions has received consid-erable interests in variational image restoration model. In this thesis, we are intended topropose several general algorithmic frameworks from the point of view of primal-dual fixedpoint algorithms based on proximity operators for solving separable convex minimizationproblem, in which one function is a composition of a convex function with a linear trans-form, and the other is differentiable with a Lipschitz continuous gradient.
Motivated from proximal forward-backward splitting (PFBS) and fixed point algorithmsbased on the proximity operator (FP~2O) for image denoising, we design a primal-dual fixedpoint algorithm based on proximity operator (PDFP~2O) and obtain a scheme with a closed-form for each iteration. We first propose PDFP~2O from our intuitions. Then we deducePDFP~2O again and express it as a fixed point iteration form based on the first optimal con-dition, the equivalent relationship between the proximity operator and the subdifferential ofa convex function, and the introduction of dual variable and two step extra inserting oper-ations. According to the fixed point form of the algorithm, we can easily get its extensionalgorithm PDFP~2Oκ. Using the firmly nonexpansive properties of the proximity operatorand with the help of a special norm over a product space, we achieve the convergence ofPDFP~2Oκ. Moreover, under some stronger assumptions, we can prove the global linear con-vergence of PDFP~2Oκ. We also give the equivalent forms of PDFP~2O and the connectionwith other existing first order methods for better understanding. Finally, we illustrate theefficiency of PDFP~2O through some numerical examples on image supperresolution, com-puterized tomographic reconstruction and parallel magnetic resonance imaging. Generallyspeaking, PDFP~2O is comparable with other state-of-the-art methods in numerical perfor-mance, while it has some advantages on parameters selection in real applications.
In many real problems, the solutions may have constraints arising from their physicalrequirements. So we design efficient algorithms for solving the separable convex minimiza-tion with convex constraint based on PDFP~2O. The constraint can be enforced by addingan indicator function to the objective function, and the function are reformulated and canbe solved with PDFP~2O. Using the separability of the function with respect to its variables, we can get a primal-dual fixed point algorithm based on proximity operator on convex set(PDFP~2O_C). Since the algorithm PDFP~2O_Ccan be recast as the original PDFP~2O for uncon-strained problem, the convergence and convergence rate analysis can be obtained directly.Meanwhile, under the assumption that the solution lies in the interior of the constrained con-vex set，using the fact that the proximal operator of an indicator function is a projectionoperator, we propose a primal-dual fixed point algorithm based on proximity operator in thiscase, called PDFP~2O_C0, by fixed point iterations similar to PDFP~2O. Then we analyze theconvergence and convergence rate of the method by using the conclusion of PDFP~2O andthe fact the projection operator is also firmly nonexpansive. Generally speaking, PDFP~2O_Ccan be used in general cases, while PDFP~2O_C0requires that the solution lies in the interiorof the constrained convex set. However, PDFP~2O_C0is simpler in form and more intuitivethan PDFP~2O_C. Finally, we illustrate the efficiency of PDFP~2O_Cand PDFP~2O_C0by sev-eral numerical experiments including computerized tomographic reconstruction and parallelmagnetic resonance imaging.
From the analysis of the convergence rate and the experiment results of CT reconstruc-tion, we can see that the convergence rate of PDFP~2O depends strongly on the conditionnumbers of the corresponding matrices, and the convergence rate of PDFP~2O will becomeworse when the condition numbers of the corresponding matrices become larger. So weconsider to accelerate PDFP~2O using preconditioning operators and propose a primal-dualfixed point algorithm based on proximity and precondition operators (PDFP~3O) by using thesimilar technique in PDFP~2O, in which we introduce two preconditioning operators. Similarto PDFP~2O, we can also analyze the convergence and the convergence rate of PDFP~3O byintroducing another special norm. We compare PDFP~3O with exact Uzawa, inexact Uzawaand non-linear inexact Uzawa, and also deduce these algorithms using the similar ideas forderiving PDFP~3O. In numerical experiments, we show that PDFP~3O is better than PDFP~2O,especially when the condition number of the problem is bad, through two problems fromthe second elliptic variational inequality problem. In simplified friction problem, we con-vert the degenerate case into the one suited for our theoretical analysis of convergence rateby using the first order optimal condition, and choose the preconditioning matrices via theintrinsic properties of the new problem. In the flow problem of a viscous plastic fluid ina pipe，we try to use conjugate gradient method to generate the effect of preconditioningmatrix in PDFP~3O.
在基于邻近算子的前向后向算子分裂算法（PFBS）和基于邻近算子的不动点算法（FP~2O）的基础上，首先从直观上得到PDFP~2O.然后利用一阶优化条件，通过引入对偶变量，利用邻近算子与次梯度的等价关系，通过两步额外的迭代，可以将提出的算法表示成算子的不动点迭代形式，并因此得到PDFP~2O的拓展版本PDFP~2Oκ.利用邻近算子的强非扩张性，在特殊构造的范数的帮助下，证明了PDFP~2Oκ的收敛性.在稍强的条件下，进一步给出了算法PDFP~2Oκ的收敛速度.接下来，通过等价变形，进一步解释了算法PDFP~2O，并给出了与其他已有算法的联系和区别.最后通过关于图像放大、CT重构、并行核磁共振成像的数值实验说明了算法的有效性.总体来说，PDFP~2O的性能和当前顶尖的算法的性能是可比较的，而PDFP~2O的参数的选择相对容易，这在求解具体的实际问题中是很有意义的.
对于很多实际问题，根据不同的物理背景，解的取值都有一定的限制.所以，进一步考虑求解带凸集约束的可分离凸优化问题.通过将凸集的约束表示成示性函数而加入目标函数中的技巧，适当重新组合，可直接利用PDFP~2O求解，利用函数的可分离性，得到PDFP~2O_C.因为PDFP~2O_C本质上就是利用PDFP~2O求解与原问题等价的无约束优化问题，根据PDFP~2O的证明结果，可以方便的得到PDFP~2O_C的收敛性以及收敛速度.在解位于凸集内部的假设条件下，利用示性函数的邻近算子为投影算子，类似于PDFP~2O的推导，通过算子的不动点迭代得到求解解位于凸集内部的可分离凸优化问题的基于邻近算子的原始对偶不动点算法（PDFP~2O_C0）.利用投影算子也是强非扩张算子的性质，并利用PDFP~2O的证明结果，得到PDFP~2O_C0的收敛性以及收敛速度.一般来说，算法PDFP~2O_C具有很好的通用性，算法PDFP~2O_C0只适用于解位于凸集内部的情形，但其迭代形式更简单、直观.最后通过CT重构和并行核磁共振成像说明了算法PDFP~2O_C和PDFP~2O_C0的有效性.
从收敛速度的估计中，以及CT重构的数值实验结果中，可以看出PDFP~2O的收敛速度和相应矩阵的条件数有关，当其中一个矩阵的条件数变差时，PDFP~2O的收敛速度会变慢.所以，进一步考虑利用预处理算子来加速，提出PDFP~3O.类似于PDFP~2O的推导，通过额外引入两个预处理算子可以得到PDFP~3O.通过引入另一个特殊构造的范数，类似于PDFP~2O的证明，可以证明PDFP~3O的收敛性与收敛速度.并进一步将PDFP~3O与精确Uzawa、不精确Uzawa算法和非线性不精确Uzawa算法比较，并利用不动点算法框架导出这些算法.最后，通过第二类椭圆变分不等式中的两个实例，说明当问题条件数较差时，PDFP~3O的确优于PDFP~2O.在简化的摩擦问题中，根据一阶优化条件，将退化的问题转化为非退化的问题；根据新问题中的迭代矩阵的内蕴性质，给出了选择预处理矩阵的方法.在管中的粘塑性流体问题中，尝试采用共轭梯度法获得预处理矩阵的效果.
In recent years, minimization of a sum of two convex functions has received consid-erable interests in variational image restoration model. In this thesis, we are intended topropose several general algorithmic frameworks from the point of view of primal-dual fixedpoint algorithms based on proximity operators for solving separable convex minimizationproblem, in which one function is a composition of a convex function with a linear trans-form, and the other is differentiable with a Lipschitz continuous gradient.
Motivated from proximal forward-backward splitting (PFBS) and fixed point algorithmsbased on the proximity operator (FP~2O) for image denoising, we design a primal-dual fixedpoint algorithm based on proximity operator (PDFP~2O) and obtain a scheme with a closed-form for each iteration. We first propose PDFP~2O from our intuitions. Then we deducePDFP~2O again and express it as a fixed point iteration form based on the first optimal con-dition, the equivalent relationship between the proximity operator and the subdifferential ofa convex function, and the introduction of dual variable and two step extra inserting oper-ations. According to the fixed point form of the algorithm, we can easily get its extensionalgorithm PDFP~2Oκ. Using the firmly nonexpansive properties of the proximity operatorand with the help of a special norm over a product space, we achieve the convergence ofPDFP~2Oκ. Moreover, under some stronger assumptions, we can prove the global linear con-vergence of PDFP~2Oκ. We also give the equivalent forms of PDFP~2O and the connectionwith other existing first order methods for better understanding. Finally, we illustrate theefficiency of PDFP~2O through some numerical examples on image supperresolution, com-puterized tomographic reconstruction and parallel magnetic resonance imaging. Generallyspeaking, PDFP~2O is comparable with other state-of-the-art methods in numerical perfor-mance, while it has some advantages on parameters selection in real applications.
In many real problems, the solutions may have constraints arising from their physicalrequirements. So we design efficient algorithms for solving the separable convex minimiza-tion with convex constraint based on PDFP~2O. The constraint can be enforced by addingan indicator function to the objective function, and the function are reformulated and canbe solved with PDFP~2O. Using the separability of the function with respect to its variables, we can get a primal-dual fixed point algorithm based on proximity operator on convex set(PDFP~2O_C). Since the algorithm PDFP~2O_Ccan be recast as the original PDFP~2O for uncon-strained problem, the convergence and convergence rate analysis can be obtained directly.Meanwhile, under the assumption that the solution lies in the interior of the constrained con-vex set，using the fact that the proximal operator of an indicator function is a projectionoperator, we propose a primal-dual fixed point algorithm based on proximity operator in thiscase, called PDFP~2O_C0, by fixed point iterations similar to PDFP~2O. Then we analyze theconvergence and convergence rate of the method by using the conclusion of PDFP~2O andthe fact the projection operator is also firmly nonexpansive. Generally speaking, PDFP~2O_Ccan be used in general cases, while PDFP~2O_C0requires that the solution lies in the interiorof the constrained convex set. However, PDFP~2O_C0is simpler in form and more intuitivethan PDFP~2O_C. Finally, we illustrate the efficiency of PDFP~2O_Cand PDFP~2O_C0by sev-eral numerical experiments including computerized tomographic reconstruction and parallelmagnetic resonance imaging.
From the analysis of the convergence rate and the experiment results of CT reconstruc-tion, we can see that the convergence rate of PDFP~2O depends strongly on the conditionnumbers of the corresponding matrices, and the convergence rate of PDFP~2O will becomeworse when the condition numbers of the corresponding matrices become larger. So weconsider to accelerate PDFP~2O using preconditioning operators and propose a primal-dualfixed point algorithm based on proximity and precondition operators (PDFP~3O) by using thesimilar technique in PDFP~2O, in which we introduce two preconditioning operators. Similarto PDFP~2O, we can also analyze the convergence and the convergence rate of PDFP~3O byintroducing another special norm. We compare PDFP~3O with exact Uzawa, inexact Uzawaand non-linear inexact Uzawa, and also deduce these algorithms using the similar ideas forderiving PDFP~3O. In numerical experiments, we show that PDFP~3O is better than PDFP~2O,especially when the condition number of the problem is bad, through two problems fromthe second elliptic variational inequality problem. In simplified friction problem, we con-vert the degenerate case into the one suited for our theoretical analysis of convergence rateby using the first order optimal condition, and choose the preconditioning matrices via theintrinsic properties of the new problem. In the flow problem of a viscous plastic fluid ina pipe，we try to use conjugate gradient method to generate the effect of preconditioningmatrix in PDFP~3O.
引文
[1] Rudin L I, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms[J]. PhysicaD: Nonlinear Phenomena,1992,60(1-4):259-268.
[2] Chambolle A, Caselles V, Cremers D, et al. An introduction to total variation for image analysis[J].Theoretical foundations and numerical methods for sparse recovery,2010,9:263-340.
[3] Cande`s E, Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory,2005,51(12):4203-4215.
[4] Cande`s E, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highlyincomplete frequency information[J]. IEEE Transactions on Information Theory,2006,52(2):489-509.
[5] Cande`s E. Compressive sampling[C]. Proceedings of the International Congress of Mathematicians:Madrid, August22-30,2006: invited lectures.2006:1433-1452.
[6] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[7]李树涛，魏丹．压缩传感综述[J]．自动化学报,2009，35(11):1369-1377.
[8]文再文,印卧涛,刘歆等.压缩感知和稀疏优化简介[J].运筹学学报,2012,16(3):49-64.
[9]许志强.压缩感知[J].中国科学:数学,2012,42(9):865-877.
[10] Compressive Sensing Resources. http://dsp.rice.edu/cs.
[11] Combettes P L, Wajs V R. Signal recovery by proximal forward-backward splitting[J]. MultiscaleModeling and Simulation,2005,4(4):1168-1200.
[12] Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators[J]. SIAM Journalon Numerical Analysis,1979,16(6):964-979.
[13] Passty G B. Ergodic convergence to a zero of the sum of monotone operators in Hilbert space[J].Journal of Mathematical Analysis and Applications,1979,72(2):383-390.
[14] Peaceman D W, Rachford, Jr H H. The numerical solution of parabolic and elliptic differentialequations[J]. Journal of the Society for Industrial and Applied Mathematics,1955,3(1):28-41.
[15] Douglas J, Rachford H H. On the numerical solution of heat conduction problems in two and threespace variables[J]. Transactions of the American mathematical Society,1956,82(2):421-439.
[16] Moreau J J. Fonctions convexes duales et points proximaux dans un espace hilbertien.(French)[J].CR Acad. Sci. Paris,1962,255:2897-2899.
[17] Hale E T, Yin W, Zhang Y. Fixed-point continuation for1-minimization: Methodology and conver-gence[J]. SIAM Journal on Optimization,2008,19(3):1107-1130.
[18] Wen Z, Yin W, Goldfarb D, et al. A fast algorithm for sparse reconstruction based on shrinkage,subspace optimization, and continuation[J]. SIAM Journal on Scientific Computing,2010,32(4):1832-1857.
[19] Figueiredo M A T, Nowak R D, Wright S J. Gradient projection for sparse reconstruction: Appli-cation to compressed sensing and other inverse problems[J]. Selected Topics in Signal Processing,IEEE Journal of,2007,1(4):586-597.
[20] Goldstein T, Osher S. The split Bregman method for L1-regularized problems[J]. SIAM Journal onImaging Sciences,2009,2(2):323-343.
[21] Getreuer P. Rudin-Osher-Fatemi Total Variation Denoising using Split Bregman[J]. Image Process-ing On Line,2012.
[22] Getreuer P. Total Variation Inpainting using Split Bregman[J]. Image Processing On Line, submitted.http://www. ipol. im/pub/algo/g tv inpainting,2012.
[23] Getreuer P. Total Variation Deconvolution using Split Bregman[J]. Image Processing On Line, sub-mitted. http://www. ipol. im/pub/algo/g tv deconvolution,2012.
[24] Eckstein J, Bertsekas D P. On the douglas-rachford splitting method and the proximal point algo-rithm for maximal monotone operators[J]. Mathematical Programming,1992,55(1-3):293-318.
[25] Setzer S. Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage[J]. Scale Spaceand Variational Methods in Computer Vision,2009,5567:464-476.
[26] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternatingdirection method of multipliers[J]. Foundations and Trends in Machine Learning,2011,3(1):1-122.
[27] Esser E. Applications of Lagrangian-based alternating direction methods and connections to splitBregman[R]. UCLA CAM Report,2009,[09-31].
[28] Zhu M, Chan T. An efficient primal-dual hybrid gradient algorithm for total variation image restora-tion[R]. UCLA CAM Report,2008:[08-34].
[29] Esser E, Zhang X, Chan T F. A general framework for a class of first order primal-dual algorithmsfor convex optimization in imaging science[J]. SIAM Journal on Imaging Sciences,2010,3(4):1015-1046.
[30] Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications toimaging[J]. Journal of Mathematical Imaging and Vision,2011,40(1):120-145.
[31] Zhang X, Burger M, Osher S. A unified primal-dual algorithm framework based on Bregman itera-tion[J]. Journal of Scientific Computing,2011,46(1):20-46.
[32] He B, Yuan X. Convergence analysis of primal-dual algorithms for a saddle-point problem: Fromcontraction perspective[J]. SIAM Journal on Imaging Sciences,2012,5(1):119-149.
[33] Bonettini S, Ruggiero V. On the convergence of primal-dual hybrid gradient algorithms for totalvariation image restoration[J]. Journal of Mathematical Imaging and Vision,2012,44(3):236-253.
[34] Glowinski R, Lions J L and Tre′molie`res R. Numerical Analysis of Variational Inequalities[M].North-Holland, Amsterdam,1981.
[35] Glowinski R. Numerical Methods for Nonlinear Variational Problems[M]. Springer-Verlag, NewYork,1984.
[36] Cheng X, Han W. Inexact Uzawa algorithms for variational inequalities of the second kind[J]. Com-puter methods in applied mechanics and engineering,2003,192(11):1451-1462.
[37] Stadler G. Semismooth Newton and augmented Lagrangian methods for a simplified friction prob-lem[J]. SIAM Journal on Optimization,2004,15(1):39-62.
[38] Nesterov Y. A method of solving a convex programming problem with convergence rate O(1/k2)[C]Soviet Mathematics Doklady,1983,27(2):372-376.
[39] Tseng P. On accelerated proximal gradient methods for convex-concave optimization[J]. submittedto SIAM Journal on Optimization,2008.
[40] Tseng P. Approximation accuracy, gradient methods, and error bound for structured convex opti-mization[J]. Mathematical programming,2010,125(2):263-295.
[41] Goldstein T, O’Donoghue B, Setzer S. Fast alternating direction optimization methods[R]. UCLACAM Report,2012,[12-35].
[42] Chen G H G, Rockafellar R T. Convergence Rates in Forward-Backward Splitting[J]. SIAM Journalon Optimization,1997,7(2):421-444.
[43] He B, Yuan X. On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating DirectionMethod[J]. SIAM Journal on Numerical Analysis,2012,50(2):700-709.
[44] Deng W, Yin W. On the global and linear convergence of the generalized alternating directionmethod of multipliers[R]. UCLA CAM Report,2012:[12-52]
[45] Luo Z Q. On the linear convergence of the alternating direction method of multipliers[J]. arXivpreprint arXiv:1208.3922,2012.
[46] Chambolle A. An algorithm for total variation minimization and applications[J]. Journal of Mathe-matical imaging and vision,2004,20(1-2):89-97.
[47] Micchelli C A, Shen L, Xu Y. Proximity algorithms for image models: denoising[J]. Inverse Prob-lems,2011,27(4):045009.
[48] Argyriou A, Micchelli C A, Pontil M, et al. Efficient first order methods for linear composite regu-larizers[J]. Arxiv preprint arXiv:1104.1436,2011.
[49] Chen D Q, Zhang H, Cheng L Z. A fast fixed point algorithm for total variation deblurring andsegmentation[J]. Journal of Mathematical Imaging and Vision,2012,43(3):167-179.
[50] Micchelli C A, Shen L, Xu Y, et al. Proximity algorithms for the L1/TV image denoising model[J].Advances in Computational Mathematics,2013,38(2):401-426.
[51] Krol A, Li S, Shen L, et al. Preconditioned alternating projection algorithms for maximum a poste-riori ECT reconstruction[J]. Inverse problems,2012,28(11):115005.
[52] Li Q, Shen L, Xu Y, et al. Multi-Step Proximity Algorithms for Solving a Class of Convex Opti-mization Problems[R]. UCLA CAM Report,2012:[12-65].
[53] Rockafellar R T. Convex analysis[M]. Princeton, NJ: Princeton University Press,1970.
[54] Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive map-pings[J]. Bull. Amer. Math. Soc,1967,73(4):591-597.
[55] Arrow K J, Hurwicz L, Uzawa H. Studies in linear and non-linear programming[M]. Stanford:Stanford Univeristy Press,1958.
[56] Chen Y, Hager W, Huang F, et al. Fast algorithms for image reconstruction with application topartially parallel MR imaging[J]. SIAM Journal on Imaging Sciences,2012,5(1):90-118.
[57] Zhang X, Burger M, Bresson X, et al. Bregmanized nonlocal regularization for deconvolution andsparse reconstruction[J]. SIAM Journal on Imaging Sciences,2010,3(3):253-276.
[58] Avinash C.. Kak, Slaney M. Principles of Computerized Tomographic Imaging[M]. Philadelphia:SIAM,2001.
[59] Blaimer M, Breuer F, Mueller M, et al. SMASH, SENSE, PILS, GRAPPA: how to choose the opti-mal method[J]. Topics in Magnetic Resonance Imaging,2004,15(4):223-236.
[60] Keeling S L, Clason C, Hintermüller M, et al. An image space approach to Cartesian based parallelMR imaging with total variation regularization[J]. Medical Image Analysis,2012,16(1):189-200.
[61] Knoll F, Clason C, Bredies K, et al. Parallel imaging with nonlinear reconstruction using variationalpenalties[J]. Magnetic Resonance in Medicine,2012,67(1):34-41.
[62] Ji J X, Son J B, Rane S D. PULSAR: A Matlab toolbox for parallel magnetic resonance imaging us-ing array coils and multiple channel receivers[J]. Concepts in Magnetic Resonance Part B: MagneticResonance Engineering,2007,31(1):24-36.
[63] Pock T, Chambolle A. Diagonal preconditioning for first order primal-dual algorithms in convexoptimization[C] Computer Vision (ICCV),2011IEEE International Conference on. IEEE,2011:1762-1769.
[64]韩渭敏，程晓良.变分不等式—基本理论、数值分析及应用[M].北京:高等教育出版社，2007.
[65] Ciarlet P G. The finite element method for elliptic problems[M]. Amsterdam: North-Holland,1978.
[66]王烈衡，许学军.有限元方法的数学基础[M].北京：科学出版社，2004.
[67] Brenner S C, Scott L R. The mathematical theory of finite element methods (third edition)[M].Springer,2008.
[68] Alberty J, Carstensen C, Funken S A. Remarks around50lines of Matlab: short finite elementimplementation[J]. Numerical Algorithms,1999,20(2-3):117-137.
[2] Chambolle A, Caselles V, Cremers D, et al. An introduction to total variation for image analysis[J].Theoretical foundations and numerical methods for sparse recovery,2010,9:263-340.
[3] Cande`s E, Tao T. Decoding by linear programming[J]. IEEE Transactions on Information Theory,2005,51(12):4203-4215.
[4] Cande`s E, Romberg J, Tao T. Robust uncertainty principles: Exact signal reconstruction from highlyincomplete frequency information[J]. IEEE Transactions on Information Theory,2006,52(2):489-509.
[5] Cande`s E. Compressive sampling[C]. Proceedings of the International Congress of Mathematicians:Madrid, August22-30,2006: invited lectures.2006:1433-1452.
[6] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory,2006,52(4):1289-1306.
[7]李树涛，魏丹．压缩传感综述[J]．自动化学报,2009，35(11):1369-1377.
[8]文再文,印卧涛,刘歆等.压缩感知和稀疏优化简介[J].运筹学学报,2012,16(3):49-64.
[9]许志强.压缩感知[J].中国科学:数学,2012,42(9):865-877.
[10] Compressive Sensing Resources. http://dsp.rice.edu/cs.
[11] Combettes P L, Wajs V R. Signal recovery by proximal forward-backward splitting[J]. MultiscaleModeling and Simulation,2005,4(4):1168-1200.
[12] Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators[J]. SIAM Journalon Numerical Analysis,1979,16(6):964-979.
[13] Passty G B. Ergodic convergence to a zero of the sum of monotone operators in Hilbert space[J].Journal of Mathematical Analysis and Applications,1979,72(2):383-390.
[14] Peaceman D W, Rachford, Jr H H. The numerical solution of parabolic and elliptic differentialequations[J]. Journal of the Society for Industrial and Applied Mathematics,1955,3(1):28-41.
[15] Douglas J, Rachford H H. On the numerical solution of heat conduction problems in two and threespace variables[J]. Transactions of the American mathematical Society,1956,82(2):421-439.
[16] Moreau J J. Fonctions convexes duales et points proximaux dans un espace hilbertien.(French)[J].CR Acad. Sci. Paris,1962,255:2897-2899.
[17] Hale E T, Yin W, Zhang Y. Fixed-point continuation for1-minimization: Methodology and conver-gence[J]. SIAM Journal on Optimization,2008,19(3):1107-1130.
[18] Wen Z, Yin W, Goldfarb D, et al. A fast algorithm for sparse reconstruction based on shrinkage,subspace optimization, and continuation[J]. SIAM Journal on Scientific Computing,2010,32(4):1832-1857.
[19] Figueiredo M A T, Nowak R D, Wright S J. Gradient projection for sparse reconstruction: Appli-cation to compressed sensing and other inverse problems[J]. Selected Topics in Signal Processing,IEEE Journal of,2007,1(4):586-597.
[20] Goldstein T, Osher S. The split Bregman method for L1-regularized problems[J]. SIAM Journal onImaging Sciences,2009,2(2):323-343.
[21] Getreuer P. Rudin-Osher-Fatemi Total Variation Denoising using Split Bregman[J]. Image Process-ing On Line,2012.
[22] Getreuer P. Total Variation Inpainting using Split Bregman[J]. Image Processing On Line, submitted.http://www. ipol. im/pub/algo/g tv inpainting,2012.
[23] Getreuer P. Total Variation Deconvolution using Split Bregman[J]. Image Processing On Line, sub-mitted. http://www. ipol. im/pub/algo/g tv deconvolution,2012.
[24] Eckstein J, Bertsekas D P. On the douglas-rachford splitting method and the proximal point algo-rithm for maximal monotone operators[J]. Mathematical Programming,1992,55(1-3):293-318.
[25] Setzer S. Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage[J]. Scale Spaceand Variational Methods in Computer Vision,2009,5567:464-476.
[26] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternatingdirection method of multipliers[J]. Foundations and Trends in Machine Learning,2011,3(1):1-122.
[27] Esser E. Applications of Lagrangian-based alternating direction methods and connections to splitBregman[R]. UCLA CAM Report,2009,[09-31].
[28] Zhu M, Chan T. An efficient primal-dual hybrid gradient algorithm for total variation image restora-tion[R]. UCLA CAM Report,2008:[08-34].
[29] Esser E, Zhang X, Chan T F. A general framework for a class of first order primal-dual algorithmsfor convex optimization in imaging science[J]. SIAM Journal on Imaging Sciences,2010,3(4):1015-1046.
[30] Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications toimaging[J]. Journal of Mathematical Imaging and Vision,2011,40(1):120-145.
[31] Zhang X, Burger M, Osher S. A unified primal-dual algorithm framework based on Bregman itera-tion[J]. Journal of Scientific Computing,2011,46(1):20-46.
[32] He B, Yuan X. Convergence analysis of primal-dual algorithms for a saddle-point problem: Fromcontraction perspective[J]. SIAM Journal on Imaging Sciences,2012,5(1):119-149.
[33] Bonettini S, Ruggiero V. On the convergence of primal-dual hybrid gradient algorithms for totalvariation image restoration[J]. Journal of Mathematical Imaging and Vision,2012,44(3):236-253.
[34] Glowinski R, Lions J L and Tre′molie`res R. Numerical Analysis of Variational Inequalities[M].North-Holland, Amsterdam,1981.
[35] Glowinski R. Numerical Methods for Nonlinear Variational Problems[M]. Springer-Verlag, NewYork,1984.
[36] Cheng X, Han W. Inexact Uzawa algorithms for variational inequalities of the second kind[J]. Com-puter methods in applied mechanics and engineering,2003,192(11):1451-1462.
[37] Stadler G. Semismooth Newton and augmented Lagrangian methods for a simplified friction prob-lem[J]. SIAM Journal on Optimization,2004,15(1):39-62.
[38] Nesterov Y. A method of solving a convex programming problem with convergence rate O(1/k2)[C]Soviet Mathematics Doklady,1983,27(2):372-376.
[39] Tseng P. On accelerated proximal gradient methods for convex-concave optimization[J]. submittedto SIAM Journal on Optimization,2008.
[40] Tseng P. Approximation accuracy, gradient methods, and error bound for structured convex opti-mization[J]. Mathematical programming,2010,125(2):263-295.
[41] Goldstein T, O’Donoghue B, Setzer S. Fast alternating direction optimization methods[R]. UCLACAM Report,2012,[12-35].
[42] Chen G H G, Rockafellar R T. Convergence Rates in Forward-Backward Splitting[J]. SIAM Journalon Optimization,1997,7(2):421-444.
[43] He B, Yuan X. On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating DirectionMethod[J]. SIAM Journal on Numerical Analysis,2012,50(2):700-709.
[44] Deng W, Yin W. On the global and linear convergence of the generalized alternating directionmethod of multipliers[R]. UCLA CAM Report,2012:[12-52]
[45] Luo Z Q. On the linear convergence of the alternating direction method of multipliers[J]. arXivpreprint arXiv:1208.3922,2012.
[46] Chambolle A. An algorithm for total variation minimization and applications[J]. Journal of Mathe-matical imaging and vision,2004,20(1-2):89-97.
[47] Micchelli C A, Shen L, Xu Y. Proximity algorithms for image models: denoising[J]. Inverse Prob-lems,2011,27(4):045009.
[48] Argyriou A, Micchelli C A, Pontil M, et al. Efficient first order methods for linear composite regu-larizers[J]. Arxiv preprint arXiv:1104.1436,2011.
[49] Chen D Q, Zhang H, Cheng L Z. A fast fixed point algorithm for total variation deblurring andsegmentation[J]. Journal of Mathematical Imaging and Vision,2012,43(3):167-179.
[50] Micchelli C A, Shen L, Xu Y, et al. Proximity algorithms for the L1/TV image denoising model[J].Advances in Computational Mathematics,2013,38(2):401-426.
[51] Krol A, Li S, Shen L, et al. Preconditioned alternating projection algorithms for maximum a poste-riori ECT reconstruction[J]. Inverse problems,2012,28(11):115005.
[52] Li Q, Shen L, Xu Y, et al. Multi-Step Proximity Algorithms for Solving a Class of Convex Opti-mization Problems[R]. UCLA CAM Report,2012:[12-65].
[53] Rockafellar R T. Convex analysis[M]. Princeton, NJ: Princeton University Press,1970.
[54] Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive map-pings[J]. Bull. Amer. Math. Soc,1967,73(4):591-597.
[55] Arrow K J, Hurwicz L, Uzawa H. Studies in linear and non-linear programming[M]. Stanford:Stanford Univeristy Press,1958.
[56] Chen Y, Hager W, Huang F, et al. Fast algorithms for image reconstruction with application topartially parallel MR imaging[J]. SIAM Journal on Imaging Sciences,2012,5(1):90-118.
[57] Zhang X, Burger M, Bresson X, et al. Bregmanized nonlocal regularization for deconvolution andsparse reconstruction[J]. SIAM Journal on Imaging Sciences,2010,3(3):253-276.
[58] Avinash C.. Kak, Slaney M. Principles of Computerized Tomographic Imaging[M]. Philadelphia:SIAM,2001.
[59] Blaimer M, Breuer F, Mueller M, et al. SMASH, SENSE, PILS, GRAPPA: how to choose the opti-mal method[J]. Topics in Magnetic Resonance Imaging,2004,15(4):223-236.
[60] Keeling S L, Clason C, Hintermüller M, et al. An image space approach to Cartesian based parallelMR imaging with total variation regularization[J]. Medical Image Analysis,2012,16(1):189-200.
[61] Knoll F, Clason C, Bredies K, et al. Parallel imaging with nonlinear reconstruction using variationalpenalties[J]. Magnetic Resonance in Medicine,2012,67(1):34-41.
[62] Ji J X, Son J B, Rane S D. PULSAR: A Matlab toolbox for parallel magnetic resonance imaging us-ing array coils and multiple channel receivers[J]. Concepts in Magnetic Resonance Part B: MagneticResonance Engineering,2007,31(1):24-36.
[63] Pock T, Chambolle A. Diagonal preconditioning for first order primal-dual algorithms in convexoptimization[C] Computer Vision (ICCV),2011IEEE International Conference on. IEEE,2011:1762-1769.
[64]韩渭敏，程晓良.变分不等式—基本理论、数值分析及应用[M].北京:高等教育出版社，2007.
[65] Ciarlet P G. The finite element method for elliptic problems[M]. Amsterdam: North-Holland,1978.
[66]王烈衡，许学军.有限元方法的数学基础[M].北京：科学出版社，2004.
[67] Brenner S C, Scott L R. The mathematical theory of finite element methods (third edition)[M].Springer,2008.
[68] Alberty J, Carstensen C, Funken S A. Remarks around50lines of Matlab: short finite elementimplementation[J]. Numerical Algorithms,1999,20(2-3):117-137.