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

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