- Analysis and Generalizations of the Linearized Bregman Method Wotao Yin (wotao.yinrice.edu) Abstract: This paper reviews the Bregman methods, analyzes the linearized Bregman method, and proposes fast generalization of the latter for solving the basis pursuit and related problems. The analysis shows that the linearized Bregman method has the exact penalty property, namely, it converges to an exact solution of the basis pursuit problem if and only if its regularization parameter $\alpha$ is greater than a certain value. The analysis is based on showing that the linearized Bregman algorithm is equivalent to gradient descent applied to a certain dual formulation. This result motivates generalizations of the algorithm enabling the use of gradient-based optimization techniques such as line search, Barzilai-Borwein steps, L-BFGS, and nonlinear conjugate gradient steps. In addition, the paper discusses the selection and update of $\alpha$. The analysis and discussions are limited to the l1-norm but can be extended to other l1-like functions. Keywords: Bregman, linearized Bregman, compressed sensing, l1 minimization, basis pursuit Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Applications -- Science and Engineering (Basic Sciences Applications ) Citation: Rice CAAM Report TR09-02, 2009 Download: [PDF]Entry Submitted: 05/28/2009Entry Accepted: 05/28/2009Entry Last Modified: 07/26/2010Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.