The Bregman Iterative Procedure

Do not confuse this with the linearized Bregman method! 

so says the Bregman Iterative Procedure site: where is featured this paper: Error Forgetting of Bregman Iteration. by  Wotao Yin and Stanley Osher. The abstract reads:

This short article analyzes an interesting property of the Bregman iterative procedure, which is

equivalent to the augmented Lagrangian method, for minimizing a convex piece-wise linear function J(x) subject to linear constraints Ax = b. The procedure obtains its solution by solving a sequence of unconstrained subproblems of minimizing J(x)+ 12kAx−bkk22, where bk is iteratively updated. In practice, the subproblems can be solved at relatively low accuracy. Let w k denote the numerical error at iteration k. If all w k are sufficiently small so that Bregman iteration identifies the optimal face, then on the optimal face, Bregman iteration enjoys an interesting error-forgetting property: the distance between the current point ˉx k and the optimal solution set X is bounded by kwk+1− wkk, independent of the numerical errors at previous iterations. This property partially explains why the Bregman iterative procedure works well for sparse optimization and, in particular, l1-minimization. The error-forgetting property is unique to piece-wise linear functions (i.e., polyhedral functions) J(x), and the results of this article appears to new to the literature of the augmented Lagrangian method.

The attendant code for this procedure can be found here.

  Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.