Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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
Published electronically: May 1, 2013
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?)


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: http://dx.doi.org/10.1090/S0025-5718-2013-02700-7
PII: S 0025-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.