Optimization Online


Analysis and Generalizations of the Linearized Bregman Method

Wotao Yin (wotao.yin***at***rice.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/2009
Entry Accepted: 05/28/2009
Entry Last Modified: 07/26/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society