Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Linearized Bregman iterations for compressed sensing

Authors: Jian-Feng Cai, Stanley Osher and Zuowei Shen
Journal: Math. Comp. 78 (2009), 1515-1536
MSC (2000): Primary 65K05, 65F22; Secondary 65T99
Published electronically: October 22, 2008
MathSciNet review: 2501061
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Finding a solution of a linear equation $ Au=f$ with various minimization properties arises from many applications. One such application is compressed sensing, where an efficient and robust-to-noise algorithm to find a minimal $ \ell_1$ norm solution is needed. This means that the algorithm should be tailored for large scale and completely dense matrices $ A$, while $ Au$ and $ A^Tu$ can be computed by fast transforms and the solution we seek is sparse. Recently, a simple and fast algorithm based on linearized Bregman iteration was proposed in [28, 32] for this purpose. This paper is to analyze the convergence of linearized Bregman iterations and the minimization properties of their limit. Based on our analysis here, we derive also a new algorithm that is proven to be convergent with a rate. Furthermore, the new algorithm is simple and fast in approximating a minimal $ \ell_1$ norm solution of $ Au=f$ as shown by numerical simulations. Hence, it can be used as another choice of an efficient tool in compressed sensing.

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

  • 1. 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)
  • 2. A. M. Bruckstein, D. L. Donoho, and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, 2008, to appear in SIAM Review.
  • 3. J.-F. Cai, R. H. Chan, L. Shen, and Z. Shen, Restoration of chopped and nodded images by framelets, SIAM J. Sci. Comput. 30 (2008), no. 3, 1205-1227.
  • 4. -, Simultaneously inpainting in image and transformed domains, 2008, preprint.
  • 5. 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
  • 6. -, Simultaneous cartoon and texture inpainting, 2008, preprint.
  • 7. J.-F. Cai and Z. Shen, Deconvolution: A wavelet frame approach, II, 2008, preprint.
  • 8. E. Candès and J. Romberg, Sparsity and incoherence in compressive sampling, Inverse Problems 23 (2007), no. 3, 969-985. MR 2329927
  • 9. E. J. Candès, Compressive sampling, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, pp. 1433-1452. MR 2275736
  • 10. 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)
  • 11. 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)
  • 12. 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
  • 13. A. Chai and Z. Shen, Deconvolution: A wavelet frame approach, Numer. Math. 106 (2007), no. 4, 529-587. MR 2317925
  • 14. 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
  • 15. 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
  • 16. J. Darbon and S. Osher, Fast discrete optimization for sparse approximations and deconvolutions, 2007, preprint.
  • 17. 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)
  • 18. 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
  • 19. R. A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity 23 (2007), 918-925. MR 2371999
  • 20. D. L. Donoho, De-noising by soft-thresholding, IEEE Trans. Inform. Theory 41 (1995), no. 3, 613-627. MR 1331258 (96b:94002)
  • 21. -, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289-1306. MR 2241189 (2007e:94013)
  • 22. D. L. Donoho and J. Tanner, Neighborliness of randomly projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA 102 (2005), no. 27, 9452-9457 (electronic). MR 2168716
  • 23. M. Elad and A. M. Bruckstein, A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Trans. Inform. Theory 48 (2002), no. 9, 2558-2567. MR 1929464 (2003h:15002)
  • 24. A. Feuer and A. Nemirovski, On sparse representation in pairs of bases, IEEE Trans. Inform. Theory 49 (2003), no. 6, 1579-1581. MR 1984950 (2004d:42051)
  • 25. 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)
  • 26. P. J. Huber, Robust regression: Asymptotics, conjectures and Monte Carlo, Ann. Statist. 1 (1973), 799-821. MR 0356373 (50:8843)
  • 27. 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)
  • 28. 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).
  • 29. M. Rudelson and R. Vershynin, Geometric approach to error-correcting codes and reconstruction of signals, Int. Math. Res. Not. (2005), no. 64, 4019-4041. MR 2206919 (2006j:94116)
  • 30. J. A. Tropp, Just relax: Convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006), no. 3, 1030-1051. MR 2238069 (2007a:94064)
  • 31. Y. Tsaig and D. L. Donono, Extensions of compressed sensing, Signal Processing 86 (2005), 533-548.
  • 32. 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.
  • 33. Y. Zhang, A simple proof for recoverability of $ \ell_1$-minimization: Go over or under?, 2005, Rice University CAAM Technical Report TR05-09.
  • 34. -, When is missing data recoverable?, 2006, Rice University CAAM Technical Report TR06-15.
  • 35. H. Zou and T. Hastie, Regularization and variable selection via the elastic net, J. R. Stat. Soc. Ser. B Stat. Methodol. 67 (2005), no. 2, 301-320. MR 2137327

Similar Articles

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

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

Additional Information

Jian-Feng Cai
Affiliation: Temasek Laboratories, National University of Singapore, 2 Science Drive 2, Singapore 117543

Stanley Osher
Affiliation: Department of Mathematics, UCLA, 520 Portola Plaza, Los Angeles, California 90095

Zuowei Shen
Affiliation: Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543

Received by editor(s): February 27, 2008
Received by editor(s) in revised form: June 25, 2008
Published electronically: October 22, 2008
Additional Notes: The first author’s research was supported by the Wavelets and Information Processing Programme under a grant from DSTA, Singapore.
The second author’s research was partially supported by ONR grant N000140710810, and by the Department of Defense, USA
The third author’s research was supported in part by Grant R-146-000-113-112 at the National University of Singapore.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society