Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

A dual split Bregman method for fast $ \ell^1$ minimization


Authors: Yi Yang, Michael Möller and Stanley Osher
Journal: Math. Comp. 82 (2013), 2061-2085
MSC (2010): Primary 49M29, 65K10, 90C25; Secondary 65F22
DOI: https://doi.org/10.1090/S0025-5718-2013-02700-7
Published electronically: May 1, 2013
MathSciNet review: 3073192
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we propose a new algorithm for fast $ \ell ^1$ minimization as frequently arising in compressed sensing. Our method is based on a split Bregman algorithm applied to the dual of the problem of minimizing $ \Vert u\Vert _1 + \frac {1}{2 \alpha } \Vert u\Vert^2$ such that $ u$ solves the under-determined linear system $ Au=f$, which was recently investigated in the context of linearized Bregman methods.

Furthermore, we provide a convergence analysis for split Bregman methods in general and show with our compressed sensing example that a split Bregman approach to the primal energy can lead to a different type of convergence than split Bregman applied to the dual, thus making the analysis of different ways to minimize the same energy interesting for a wide variety of optimization problems.


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

  • 1. A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci 2 (2009), 183-202. MR 2486527 (2010d:35390)
  • 2. M. Burger, G. Gilboa, S. Osher, and J. Xu, Nonlinear inverse scale space methods, Comm. Math. Sci. 4 (2006), 179-212. MR 2204083 (2006i:35177)
  • 3. M. Burger, M. Moeller, M. Benning, and S. Osher, An adaptive inverse scale space method for compressed sensing, Math. Comp. 82 (2013), 269-299. MR 2983025
  • 4. M. Burger, E. Resmerita, and L. He, Error estimation for Bregman iterations and inverse scale space methods in image restoration, Computing 81 (2007), 109-135. MR 2354192 (2008k:94002)
  • 5. J. Cai, S. Osher, and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2008), no. 267, 1515-1536. MR 2501061
  • 6. -, Convergence of the linearized Bregman iteration for $ \ell ^1$-norm minimization, Math. Comp. 78 (2009), no. 268, 2127-2136. MR 2521281 (2010k:65111)
  • 7. -, Split Bregman methods and frame based image restoration, Multiscale Modeling Simulation 8 (2010), no. 2, 337. MR 2581025 (2011a:94016)
  • 8. E.J. Candes and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2004), 4203-4215. MR 2243152 (2007b:94313)
  • 9. -, Near-optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inform. Theory 52 (2004), 5406-5425. MR 2300700 (2008c:94009)
  • 10. D.L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), 1289-1306. MR 2241189 (2007e:94013)
  • 11. D.L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $ \ell ^1$ minimization, Proc. Natl. Acad. Sci. USA 100 (2003), 2197-2202. MR 1963681 (2004c:94068)
  • 12. I. Ekeland and R. Temam, Convex analysis and variational problems, corrected reprint edition, SIAM, Philadelphia, 1999. MR 1727362 (2000j:49001)
  • 13. E. Esser, Primal dual algorithms for convex models and applications to image restoration, registration and nonlocal inpainting, Ph.D. thesis, UCLA CAM (10-31), June 2010.
  • 14. T. Goldstein and S. Osher, The split Bregman method for $ \ell ^1$ regularized problems, SIAM J. Imaging Sci. 2 (2009), 323-343. MR 2496060 (2010e:65087)
  • 15. E. T. Hale, W. Yin, and Y. Zhang, A fixed-point continuation method for $ \ell ^1$-regularized minimization with applications to compressed sensing, Rice CAM Report TR07-07, July 2007.
  • 16. B. S. He and X. M. Yuan, On convergence rate of the Douglas-Rachford operator splitting method, Mathematical Programming, under revision.
  • 17. -, On the $ O(1/n)$ convergence rate of Douglas-Rachford alternating direction method, SIAM J. Numer. Anal. 50 (2012), 700-709.
  • 18. B. Huang, S. Ma, and D. Goldfarb, Accelerated linearized Bregman method, J. Sci. Comput. 54 (2013), no. 2-3, 428-453. MR 3011366
  • 19. M.J. Lai and W. Yin, Augmented $ \ell ^1$ and nuclear-norm models with a globally linearly convergent algorithm, Submitted, 2012.
  • 20. M. Moeller, T. Wittman, A.L. Bertozzi, and M. Burger, A variational approach for sharpening high dimensional images, J. Imaging Sci. 5 (2012), 150-178. MR 2902660
  • 21. S. Osher, M. Burger, D. Goldfarb, J. Xu, and W. Yin, An iterative regularization method for total variation-based image restoration, SIAM Multiscale Model. Simul. 4 (2005), 460-489. MR 2162864 (2006c:49051)
  • 22. S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci. 8 (2010), 93-111. MR 2655902 (2011c:90098)
  • 23. S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, SSVM '09, Springer-Verlag, 2009, pp. 464-476.
  • 24. W. Yin, Analysis and generalizations of the linearized Bregman method, SIAM J. Imaging Sci. 3 (2010), no. 4, 856-877. MR 2735964 (2011j:68172)
  • 25. 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), 143-168. MR 2475828 (2010f:90170)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 49M29, 65K10, 90C25, 65F22

Retrieve articles in all journals with MSC (2010): 49M29, 65K10, 90C25, 65F22


Additional Information

Yi Yang
Affiliation: Department of Mathematics, University of California Los Angeles, Portola Plaza, Los Angeles, California 90095
Email: yyang@math.ucla.edu

Michael Möller
Affiliation: Westfälische Wilhelms-Universität Münster, Institut für Numerische und Angewandte Mathematik, Einsteinstr, 62, D 48149 Münster, Germany
Email: m.moeller@gmx.net

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

DOI: https://doi.org/10.1090/S0025-5718-2013-02700-7
Keywords: $\ell^1$ minimization, optimization algorithms, sparsity, compressed sensing, calculus of variation
Received by editor(s): September 21, 2011
Received by editor(s) in revised form: March 15, 2012
Published electronically: May 1, 2013
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society