Abstract
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−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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arrow, K.J., Hurwicz, L., Uzawa, H.: Studies in Linear and Non-Linear Programming. Stanford University Press, Stanford (1958)
Avinash, C., Malcolm, S.: Principles of Computerized Tomographic Imaging. Society for Industrial and Applied Mathematics, Philadelphia (2001)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm with application to wavelet-based image deblurring. In: IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 693–696 (2009)
Becker, S., Bobin, J., Candès, E.: Nesta: a fast and accurate first-order method for sparse recovery (2009)
Borghi, A., Darbon, J., Peyronnet, S., Chan, T.F., Osher, S.: A simple compressive sensing algorithm for parallel many-core architectures. CAM Report 08-64, UCLA (2008)
Bramble, J.H., Pasciak, J.E., Vassilev, A.T.: Analysis of the inexact Uzawa algorithm for saddle point problems. SIAM J. Numer. Anal. 34(3), 1072–1092 (1997)
Bregman, L.: The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math Phys. 7, 200–217 (1967)
Cai, J.-F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956–1982 (2010)
Cai, J.-F., Osher, S., Shen, Z.: Convergence of the linearized Bregman iteration for ℓ 1-norm minimization. Math. Comput. 78, 2127–2136 (2009)
Cai, J.-F., Osher, S., Shen, Z.: Split Bregman method and frame based image restoration. CAM Report 09-28, UCLA, March 2009
Cai, J.-F., Osher, S., Shen, Z.: Linearized Bregman iterations for frame-based image deblurring. SIAM J. Imag. Sci. 2(1), 226–252 (2009)
Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. (2008, to appear)
Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006)
Censor, Y., Lent, A.: An iterative row-action method for interval convex programming. J. Optim. Theory Appl. 34(3), 321–353 (1981)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imag. Vis. 20, 89–97 (2004)
Chan, T.F., Golub, G.H., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. Math. Oper. Res. 219, 241–252 (1996)
Chen, G., Teboulle, M.: Convergence analysis of a proximal like minimization algorithm using Bregman functions. SIAM J. Optim., 3 (1993)
Chen, G., Teboulle, M.: A proximal-based decomposition method for convex minimization problems. Math. Program. 64(1), 81–101 (1994)
Chen, S.S., Donoho, David L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998)
Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4) (2005)
Darbon, J., Osher, S.: Fast discrete optimization for sparse approximations and deconvolutions. Preprint, UCLA (2007)
Daubechies, I., Defrise, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57(11), 1413–1457 (2004)
Donoho, D.L.: Compressed sensing. IEEE. Trans. Inf. Theory 52, 1289–1306 (2006)
Douglas, J., Rachford, H.H.: On the numerical solutions of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 1, 97–116 (1976)
Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)
Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. CAM Report 09-31, UCLA, April 2009
Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for TV minimization. CAM Report 09-67, UCLA, August 2009
Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Proces. 1(4), 586–597 (2007)
Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems. North-Holland, Amsterdam (1983)
Glowinski, R., Le Tallec, P.: Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989)
Goldstein, T., Bresson, X., Osher, S.: Geometric applications of the split Bregman method: segmentation and surface reconstruction. UCLA CAM Report, 09-06, February (2009)
Goldstein, T., Osher, S.: The split Bregman method for l 1 regularized problems. SIAM J. Imag. Sci., 2 (2009)
Guo, X., Li, F., Michael, K.Ng.: A fast L1-TV algorithm for image restoration. ICM Technical Report 08-13, Hong Kong Baptist University, November 2008
Hale, E.T., Yin, W., Zhang, Y.: A fixed-point continuation method for l1-regularized minimization with applications to compressed sensing. SIAM J. Optim. 19, 1107–1130 (2008)
Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)
Kim, S., Koh, K., Lustig, M., Boyd, S., Gorinevsky, D.: An interior-point method for large-scale l 1-regularized least squares. IEEE J. Sel. Top. Signal Proces. 1(4), 606–617 (2007)
Lemaréchal, C., Sagastizábal, C.: Practical aspects of the Moreau-Yosida regularization, I: Theoretical properties (1994)
Li, Y., Osher, S.: Coordinate descent optimization for ℓ 1 minimization with application to compressed sensing; a greedy algorithm. Inverse Probl. Imaging 3(3), 487–503 (2009)
Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization. Technical Report, Columbia University (2008)
Moreau, J.-J.: Fonctions convexes duales et points proximaux dans un espace hilbertien. C. R. Acad. Sci. Paris Ser. A Math. 255, 2897–2899 (1962)
Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation based image restoration. Multiscale Model. Simul. 4(2), 460–489 (2005)
Osher, S., Mao, Y., Dong, B., Yin, W.: Fast linearized Bregman iteration for compressive sensing and sparse denoising. Commun. Math. Sci. 8(1), 93–111 (2010)
Powell, M.J.D.: A method for nonlinear constraints in minimization problems. Optimization (1972)
Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 82, 421–439 (1956)
Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Setzer, S.: Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage. In: Morken, K., Lysaker, M., Lie, K.-A., Tai, X.-C. (eds.) Scale Space and Variational Methods in Computer Vision. LNCS, vol. 5567, pp. 464–476. Springer, Berlin (2009)
Tai, X.-C., Wu, C.: Augmented Lagrangian method, dual methods and split Bregman iteration for ROF model. CAM Report 09-05, UCLA, January 2009
Yang, J., Zhang, Y., Yin, W.: An efficient TV-L1 algorithm for deblurring multichannel images corrupted by impulsive noise. SIAM J. Sci. Comput. 31(4) (2009)
Yin, W.: Analysis and generalizations of the linearized Bregman method. CAAM Report, Rice University (2009)
Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for ℓ 1 minimization with applications to compressed sensing. SIAM J. Imag. Sci. 1, 143–168 (2008)
Zhang, X., Burger, M., Bresson, X., Osher, S.: Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. CAM Report 09-03, UCLA, January 2009
Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. CAM Report 08-34, UCLA, May 2008
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Zhang, X., Burger, M. & Osher, S. A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration. J Sci Comput 46, 20–46 (2011). https://doi.org/10.1007/s10915-010-9408-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-010-9408-8