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)

 

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
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?)


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