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

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

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
MR Author ID: 292105

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.