Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Convergence of the linearized Bregman iteration for $ \ell_1$-norm minimization


Authors: Jian-Feng Cai, Stanley Osher and Zuowei Shen
Journal: Math. Comp. 78 (2009), 2127-2136
MSC (2000): Primary 65K05, 65F22
DOI: https://doi.org/10.1090/S0025-5718-09-02242-X
Published electronically: March 6, 2009
MathSciNet review: 2521281
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: One of the key steps in compressed sensing is to solve the basis pursuit problem $ \min_{u\in\mathbb{R}^n}\{\Vert u\Vert _1:Au=f\}$. Bregman iteration was very successfully used to solve this problem in [40]. Also, a simple and fast iterative algorithm based on linearized Bregman iteration was proposed in [40], which is described in detail with numerical simulations in [35]. A convergence analysis of the smoothed version of this algorithm was given in [11]. The purpose of this paper is to prove that the linearized Bregman iteration proposed in [40] for the basis pursuit problem indeed converges.


References [Enhancements On Off] (What's this?)

  • 1. D. P. Bertsekas, Constrained optimization and Lagrange multiplier methods, Computer Science and Applied Mathematics, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1982. MR 690767 (84k:90068)
  • 2. D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, Massachussets, 1999.
  • 3. L. M. Brègman, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, Z. Vyčisl. Mat. i Mat. Fiz. 7 (1967), 620-631. MR 0215617 (35:6457)
  • 4. M. Burger, E. Resmerita, and L. He, Error estimation for Bregman iterations and inverse scale space methods in image restoration, Computing 81 (2007), no. 2-3, 109-135. MR 2354192 (2008k:94002)
  • 5. J.-F. Cai, E.J. Candès, and Z. Shen, A singular value thresholding algorithm for matrix completion, 2008, preprint.
  • 6. J.-F. Cai, R. Chan, L. Shen, and Z. Shen, Restoration of chopped and nodded images by framelets, SIAM J. Sci. Comput. 30 (2008), no. 3, 1205-1227. MR 2398862
  • 7. J.-F. Cai, R. H. Chan, L. Shen, and Z. Shen, Convergence analysis of tight framelet approach for missing data recovery, Adv. Comput. Math. (to appear), 2008.
  • 8. -, Simultaneously inpainting in image and transformed domains, 2008, preprint.
  • 9. J.-F. Cai, R. H. Chan, and Z. Shen, A framelet-based image inpainting algorithm, Appl. Comput. Harmon. Anal. 24 (2008), no. 2, 131-149. MR 2393979
  • 10. -, Simultaneous cartoon and texture inpainting, 2008, preprint.
  • 11. J.-F. Cai, S. Osher, and Z. Shen, Linearized Bregman iterations for compressed sensing, 2008, Math. Comp., to appear; see also UCLA CAM Report (08-06).
  • 12. -, Linearized Bregman iterations for frame-based image deblurring, 2008, preprint.
  • 13. J.-F. Cai and Z. Shen, Deconvolution: A wavelet frame approach, II, 2008, preprint.
  • 14. E. J. Candès, Compressive sampling, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, pp. 1433-1452. MR 2275736
  • 15. E. J. Candès and J. Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions, Found. Comput. Math. 6 (2006), no. 2, 227-254. MR 2228740 (2007a:94035)
  • 16. E. J. Candès, J. Romberg, and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489-509. MR 2236170 (2007e:94020)
  • 17. E. J. Candes and T. Tao, Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406-5425. MR 2300700
  • 18. E. Cetin, Reconstruction of signals from Fourier transform samples, Signal Processing, 16 (1989), 129-148. MR 991553 (90c:94008)
  • 19. -, An iterative algorithm for signal reconstruction from bispectrum, IEEE Trans. Signal Proc., 39 (1991), 2621-2628.
  • 20. A. Chai and Z. Shen, Deconvolution: A wavelet frame approach, Numer. Math. 106 (2007), no. 4, 529-587. MR 2317925 (2008i:42067)
  • 21. P. L. Combettes and J.-C. Pesquet, Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Opt. 18 (2007), no. 4, 1351-1376 (electronic). MR 2373305 (2008k:90091)
  • 22. P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168-1200 (electronic). MR 2203849
  • 23. J. Darbon and S. Osher, Fast discrete optimization for sparse approximations and deconvolutions, 2007, preprint.
  • 24. I. Daubechies, M. Defrise, and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. 57 (2004), no. 11, 1413-1457. MR 2077704 (2005k:65106)
  • 25. I. Daubechies, G. Teschke, and L. Vese, Iteratively solving linear inverse problems under general convex constraints, Inverse Probl. Imaging 1 (2007), no. 1, 29-46. MR 2262744
  • 26. D. L. Donoho, De-noising by soft-thresholding, IEEE Trans. Inform. Theory 41 (1995), no. 3, 613-627. MR 1331258 (96b:94002)
  • 27. -, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289-1306. MR 2241189 (2007e:94013)
  • 28. M. Fortin and R. Glowinski, Augmented Lagrangian methods, Studies in Mathematics and its Applications, vol. 15, North-Holland Publishing Co., Amsterdam, 1983, Applications to the numerical solution of boundary value problems, Translated from the French by B. Hunt and D. C. Spicer. MR 724072 (85a:49004)
  • 29. T. Goldstein and S. Osher, The split Bregman algorithm for l1 regularized problems, 2008, UCLA CAM Reports (08-29).
  • 30. M. R. Hestenes, Multiplier and gradient methods, J. Optimization Theory Appl. 4 (1969), 303-320. MR 0271809 (42:6690)
  • 31. J.-B. Hiriart-Urruty and C. Lemaréchal, Convex analysis and minimization algorithms. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305, Springer-Verlag, Berlin, 1993, Fundamentals. MR 1261420 (95m:90001)
  • 32. P. J. Huber, Robust regression: asymptotics, conjectures and Monte Carlo, Ann. Statist. 1 (1973), 799-821. MR 0356373 (50:8843)
  • 33. K. Ito and K. Kunisch, The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces, Math. Programming 46 (1990), no. 3, (Ser. A), 341-360. MR 1054143 (91i:90062)
  • 34. S. Osher, M. Burger, D. Goldfarb, J. Xu, and W. Yin, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul. 4 (2005), no. 2, 460-489 (electronic). MR 2162864 (2006c:49051)
  • 35. S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized bregman iteration for compressed sensing and sparse denoising, 2008, UCLA CAM Reports (08-37).
  • 36. M. J. D. Powell, A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele, 1968), Academic Press, London, 1969, pp. 283-298. MR 0272403 (42:7284)
  • 37. F. Schöpfer, A. K. Louis, and T. Schuster, Nonlinear iterative methods for linear ill-posed problems in Banach spaces, Inverse Problems 22 (2006), no. 1, 311-329. MR 2194197 (2006j:65151)
  • 38. Y. Tsaig and D. L. Donono, Extensions of compressed sensing, Signal Processing 86 (2005), 533-548.
  • 39. W. Yin, On linearized Bregman iterative algorithms, private communication.
  • 40. W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for $ \ell_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143-168.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65K05, 65F22

Retrieve articles in all journals with MSC (2000): 65K05, 65F22


Additional Information

Jian-Feng Cai
Affiliation: Temasek Laboratories, National University of Singapore, 2 Science Drive 2, Singapore 117543
Email: tslcaij@nus.edu.sg

Stanley Osher
Affiliation: Department of Mathematics, UCLA, 520 Portola Plaza, Los Angeles, California 90095
Email: sjo@math.ucla.edu

Zuowei Shen
Affiliation: Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543
Email: matzuows@nus.edu.sg

DOI: https://doi.org/10.1090/S0025-5718-09-02242-X
Received by editor(s): July 21, 2008
Received by editor(s) in revised form: November 6, 2008
Published electronically: March 6, 2009
Additional Notes: Research supported by the Wavelets and Information Processing Programme under a grant from DSTA, Singapore.
Research partially supported by ONR grant N000140710810, and by the Department of Defense
Research supported by Grant R-146-000-113-112 from the National University of Singapore.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society