Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Bregman method
Iterative algorithm to solve certain convex optimization problems involving regularization

The Bregman method, introduced by Lev M. Bregman in 1967, is an iterative algorithm designed to solve certain convex optimization problems involving regularization. It operates as a row-action method by accessing constraint functions individually, making it well-suited for large-scale problems where constraints can be enumerated efficiently. The Bregman method is especially effective for regularizers like the ℓ1 norm, benefiting from a fast convergence due to an error-cancellation effect, which enhances performance in practical applications.

We don't have any images related to Bregman method yet.
We don't have any YouTube videos related to Bregman method yet.
We don't have any PDF documents related to Bregman method yet.
We don't have any Books related to Bregman method yet.
We don't have any archived web articles related to Bregman method yet.

Algorithm

In order to be able to use the Bregman method, one must frame the problem of interest as finding min u J ( u ) + f ( u ) {\displaystyle \min _{u}J(u)+f(u)} , where J {\displaystyle J} is a regularizing function such as ℓ 1 {\displaystyle \ell _{1}} .4

The Bregman distance is defined as D p ( u , v ) := J ( u ) − ( J ( v ) + ⟨ p , u − v ⟩ ) {\displaystyle D^{p}(u,v):=J(u)-(J(v)+\langle p,u-v\rangle )} where p {\displaystyle p} belongs to the subdifferential of J {\displaystyle J} at u {\displaystyle u} (which we denoted ∂ J ( u ) {\displaystyle \partial J(u)} ).56 One performs the iteration u k + 1 := min u ( α D ( u , u k ) + f ( u ) ) {\displaystyle u_{k+1}:=\min _{u}(\alpha D(u,u_{k})+f(u))} , with α {\displaystyle \alpha } a constant to be chosen by the user (and the minimization performed by an ordinary convex optimization algorithm),7 or u k + 1 := min u ( D p k ( u , u k ) + f ( u ) ) {\displaystyle u_{k+1}:=\min _{u}(D^{p_{k}}(u,u_{k})+f(u))} , with p k {\displaystyle p_{k}} chosen each time to be a member of ∂ J ( u k ) {\displaystyle \partial J(u_{k})} .8

The algorithm starts with a pair of primal and dual variables. Then, for each constraint a generalized projection onto its feasible set is performed, updating both the constraint's dual variable and all primal variables for which there are non-zero coefficients in the constraint functions gradient. In case the objective is strictly convex and all constraint functions are convex, the limit of this iterative projection converges to the optimal primal dual pair.

In the case of a basis pursuit-type problem min x : A x = b ( | x | 1 + 1 2 α | x | 2 2 ) {\displaystyle \min _{x:Ax=b}(|x|_{1}+{\frac {1}{2\alpha }}|x|_{2}^{2})} , the Bregman method is equivalent to ordinary gradient descent on the dual problem min y ( − b t y + α 2 | A t y − Proj [ − 1 , 1 ] n ( A t y ) | 2 ) {\displaystyle \min _{y}(-b^{t}y+{\frac {\alpha }{2}}|A^{t}y-{\text{Proj}}_{[-1,1]^{n}}(A^{t}y)|^{2})} .9 An exact regularization-type effect also occurs in this case; if α {\displaystyle \alpha } exceeds a certain threshold, the optimum value of x {\displaystyle x} is precisely the optimum solution of min x : A x = b | x | 1 {\displaystyle \min _{x:Ax=b}|x|_{1}} .1011

Applications

The Bregman method or its generalizations can be applied to:

Generalizations and drawbacks

The method has links to the method of multipliers and dual ascent method (through the so-called Bregman alternating direction method of multipliers,2425 generalizing the alternating direction method of multipliers26) and multiple generalizations exist.

One drawback of the method is that it is only provably convergent if the objective function is strictly convex. In case this can not be ensured, as for linear programs or non-strictly convex quadratic programs, additional methods such as proximal gradient methods have been developed. In the case of the Rudin-Osher-Fatemi model of image denoising, the Bregman method provably converges.27

Some generalizations of the Bregman method include:

Linearized Bregman

In the Linearized Bregman method, one linearizes the intermediate objective functions D p ( u , u k ) + f ( u ) {\displaystyle D^{p}(u,u_{k})+f(u)} by replacing the second term with f ( u k ) + ⟨ f ′ ( u k ) , u − u k ⟩ {\displaystyle f(u_{k})+\langle f'(u_{k}),u-u_{k}\rangle } (which approximates the second term near u k {\displaystyle u_{k}} ) and adding the penalty term 1 2 δ | u − u k | 2 2 {\displaystyle {\frac {1}{2\delta }}|u-u_{k}|_{2}^{2}} for a constant δ {\displaystyle \delta } . The result is much more computationally tractable, especially in basis pursuit-type problems.3233 In the case of a generic basis pursuit problem min μ | u | 1 + 1 2 | A u − f | 2 2 {\displaystyle \min \mu |u|_{1}+{\frac {1}{2}}|Au-f|_{2}^{2}} , one can express the iteration as v k + 1 := v k + A t ( f − A u k ) , u k + 1 , i := δ   shrink ( v k , i , μ ) {\displaystyle v_{k+1}:=v_{k}+A^{t}(f-Au_{k}),u_{k+1,i}:=\delta ~{\text{shrink}}(v_{k,i},\mu )} for each component i {\displaystyle i} , where we define shrink ( y , a ) := { y − a , y ∈ ( a , ∞ ) 0 , y ∈ [ − a , a ] y + a , y ∈ ( − ∞ , − a ) {\displaystyle {\text{shrink}}(y,a):={\begin{cases}y-a,&y\in (a,\infty )\\0,&y\in [-a,a]\\y+a,&y\in (-\infty ,-a)\end{cases}}} .34

Sometimes, when running the Linearized Bregman method, there are periods of "stagnation" where the residual is almost constant. To alleviate this issue, one can use the Linearized Bregman method with kicking, where one essentially detects the beginning of a stagnation period, then predicts and skips to the end of it.3536

Since Linearized Bregman is mathematically equivalent to gradient descent, it can be accelerated with methods to accelerate gradient descent, such as line search, L-BGFS, Barzilai-Borwein steps, or the Nesterov method; the last has been proposed as the accelerated linearized Bregman method.3738

Split Bregman

The Split Bregman method solves problems of the form min u | Φ ( u ) | 1 + H ( u ) {\displaystyle \min _{u}|\Phi (u)|_{1}+H(u)} , where Φ {\displaystyle \Phi } and H {\displaystyle H} are both convex,39 particularly problems of the form min u | Φ u | 1 + | K u − f | 2 {\displaystyle \min _{u}|\Phi u|_{1}+|Ku-f|^{2}} .40 We start by rewriting it as the constrained optimization problem min u : d = Φ ( u ) | d | 1 + H ( u ) {\displaystyle \min _{u:d=\Phi (u)}|d|_{1}+H(u)} , then relax it into min u , d | d | 1 + H ( u ) + λ 2 | d − Φ ( u ) | 2 2 {\displaystyle \min _{u,d}|d|_{1}+H(u)+{\frac {\lambda }{2}}|d-\Phi (u)|_{2}^{2}} where λ {\displaystyle \lambda } is a constant. By defining J ( u , d ) := | d | + H ( u ) {\displaystyle J(u,d):=|d|+H(u)} , one reduces the problem to one that can be solved with the ordinary Bregman algorithm.4142

The Split Bregman method has been generalized to optimization over complex numbers using Wirtinger derivatives.43

References

  1. Xiong, Kai; Zhao, Guanghui; Shi, Guangming; Wang, Yingbin (2019-09-12). "A Convex Optimization Algorithm for Compressed Sensing in a Complex Domain: The Complex-Valued Split Bregman Method". Sensors. 19 (20) (published 18 Oct 2019): 4540. Bibcode:2019Senso..19.4540X. doi:10.3390/s19204540. PMC 6832202. PMID 31635423. https://www.researchgate.net/publication/336665179 ↩

  2. Bregman L. "A Relaxation Method of Finding a Common Point of Convex Sets and its Application to Problems of Optimization". Dokl. Akad. Nauk SSSR, v. 171, No. 5, 1966, p.p. 1019-1022. (English translation: Soviet Math. Dokl., v. 7, 1966, p.p. 1578-1581) ↩

  3. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  4. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  5. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  6. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  7. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  8. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  9. Yin, Wotao (28 May 2009). "Analysis and Generalizations of the Linearized Bregman Method" (PDF). SIAM Journal on Imaging Sciences. 3 (4): 856–877. doi:10.1137/090760350. Archived from the original (PDF) on 2017-07-05. Retrieved 16 Apr 2021. https://web.archive.org/web/20170705134816/ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf ↩

  10. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  11. Yin, Wotao (28 May 2009). "Analysis and Generalizations of the Linearized Bregman Method" (PDF). SIAM Journal on Imaging Sciences. 3 (4): 856–877. doi:10.1137/090760350. Archived from the original (PDF) on 2017-07-05. Retrieved 16 Apr 2021. https://web.archive.org/web/20170705134816/ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf ↩

  12. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  13. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  14. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  15. Xiong, Kai; Zhao, Guanghui; Shi, Guangming; Wang, Yingbin (2019-09-12). "A Convex Optimization Algorithm for Compressed Sensing in a Complex Domain: The Complex-Valued Split Bregman Method". Sensors. 19 (20) (published 18 Oct 2019): 4540. Bibcode:2019Senso..19.4540X. doi:10.3390/s19204540. PMC 6832202. PMID 31635423. https://www.researchgate.net/publication/336665179 ↩

  16. Goldstein, Tom; Osher, Stanley (2 Jun 2008). "The Split Bregman Method for L1-Regularized Problems". SIAM J. Imaging Sci. 2 (2): 323–343. doi:10.1137/080725891. Retrieved 22 Apr 2021. https://www.researchgate.net/publication/220124333 ↩

  17. Xiong, Kai; Zhao, Guanghui; Shi, Guangming; Wang, Yingbin (2019-09-12). "A Convex Optimization Algorithm for Compressed Sensing in a Complex Domain: The Complex-Valued Split Bregman Method". Sensors. 19 (20) (published 18 Oct 2019): 4540. Bibcode:2019Senso..19.4540X. doi:10.3390/s19204540. PMC 6832202. PMID 31635423. https://www.researchgate.net/publication/336665179 ↩

  18. Jiang, Chunzhi (May 2015). "Comparison of Variable Penalty ADMM with Split Bregman Method on Hyperspectral Imaging Problems". Archived from the original on 2020-03-23. Retrieved 20 Apr 2021. https://etda.libraries.psu.edu/files/final_submissions/9702 ↩

  19. Yin, Wotao (28 May 2009). "Analysis and Generalizations of the Linearized Bregman Method" (PDF). SIAM Journal on Imaging Sciences. 3 (4): 856–877. doi:10.1137/090760350. Archived from the original (PDF) on 2017-07-05. Retrieved 16 Apr 2021. https://web.archive.org/web/20170705134816/ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf ↩

  20. Boyd, Stephen; Parikh, Neal; Chu, Eric; Peleato, Borja; Eckstein, Jonathan (19 Nov 2010). "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers". Foundations and Trends in Machine Learning. 3: 1–122. CiteSeerX 10.1.1.722.981. doi:10.1561/2200000016. /wiki/CiteSeerX_(identifier) ↩

  21. Boyd, Stephen; Parikh, Neal; Chu, Eric; Peleato, Borja; Eckstein, Jonathan (19 Nov 2010). "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers". Foundations and Trends in Machine Learning. 3: 1–122. CiteSeerX 10.1.1.722.981. doi:10.1561/2200000016. /wiki/CiteSeerX_(identifier) ↩

  22. Huang, Bo; Ma, Shiqian; Goldfarb, Donald (27 Jun 2011). "Accelerated Linearized Bregman Method". Journal of Scientific Computing. 54 (2–3). Plenum Press (published 1 Feb 2013): 428–453. arXiv:1106.5413. doi:10.1007/s10915-012-9592-9. ISSN 0885-7474. S2CID 14781930. /wiki/Plenum_Press ↩

  23. Boyd, Stephen; Parikh, Neal; Chu, Eric; Peleato, Borja; Eckstein, Jonathan (19 Nov 2010). "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers". Foundations and Trends in Machine Learning. 3: 1–122. CiteSeerX 10.1.1.722.981. doi:10.1561/2200000016. /wiki/CiteSeerX_(identifier) ↩

  24. Wang, Huahua; Banerjee, Arindam (13 Jun 2013). "Bregman alternating direction method of multipliers". NIPS'14: Proceedings of the 27th International Conference on Neural Information Processing Systems. 2: 2816–2824. arXiv:1306.3203. /wiki/ArXiv_(identifier) ↩

  25. Jiang, Chunzhi (May 2015). "Comparison of Variable Penalty ADMM with Split Bregman Method on Hyperspectral Imaging Problems". Archived from the original on 2020-03-23. Retrieved 20 Apr 2021. https://etda.libraries.psu.edu/files/final_submissions/9702 ↩

  26. Boyd, Stephen; Parikh, Neal; Chu, Eric; Peleato, Borja; Eckstein, Jonathan (19 Nov 2010). "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers". Foundations and Trends in Machine Learning. 3: 1–122. CiteSeerX 10.1.1.722.981. doi:10.1561/2200000016. /wiki/CiteSeerX_(identifier) ↩

  27. Jia, Rong-Qing (3 Oct 2008). "Convergence analysis of the Bregman method for the variational model of image denoising" (PDF). Applied and Computational Harmonic Analysis. 27 (3) (published Nov 2009): 367–379. doi:10.1016/j.acha.2009.05.002. Retrieved 22 Apr 2021. https://sites.ualberta.ca/~rjia/Paper06-10/JZZ09.pdf ↩

  28. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  29. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  30. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  31. Yin, Wotao (8 Dec 2009). "The Bregman Methods: Review and New Results" (PDF). Archived (PDF) from the original on 2010-06-13. Retrieved 16 Apr 2021. https://www.caam.rice.edu/~optimization/L1/bregman/WotaoYin_Bregman_SIAMPDE_09.pdf ↩

  32. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  33. Yin, Wotao (28 May 2009). "Analysis and Generalizations of the Linearized Bregman Method" (PDF). SIAM Journal on Imaging Sciences. 3 (4): 856–877. doi:10.1137/090760350. Archived from the original (PDF) on 2017-07-05. Retrieved 16 Apr 2021. https://web.archive.org/web/20170705134816/ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf ↩

  34. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  35. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  36. Yin, Wotao (28 May 2009). "Analysis and Generalizations of the Linearized Bregman Method" (PDF). SIAM Journal on Imaging Sciences. 3 (4): 856–877. doi:10.1137/090760350. Archived from the original (PDF) on 2017-07-05. Retrieved 16 Apr 2021. https://web.archive.org/web/20170705134816/ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf ↩

  37. Yin, Wotao (28 May 2009). "Analysis and Generalizations of the Linearized Bregman Method" (PDF). SIAM Journal on Imaging Sciences. 3 (4): 856–877. doi:10.1137/090760350. Archived from the original (PDF) on 2017-07-05. Retrieved 16 Apr 2021. https://web.archive.org/web/20170705134816/ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf ↩

  38. Huang, Bo; Ma, Shiqian; Goldfarb, Donald (27 Jun 2011). "Accelerated Linearized Bregman Method". Journal of Scientific Computing. 54 (2–3). Plenum Press (published 1 Feb 2013): 428–453. arXiv:1106.5413. doi:10.1007/s10915-012-9592-9. ISSN 0885-7474. S2CID 14781930. /wiki/Plenum_Press ↩

  39. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  40. Goldstein, Tom; Osher, Stanley (2 Jun 2008). "The Split Bregman Method for L1-Regularized Problems". SIAM J. Imaging Sci. 2 (2): 323–343. doi:10.1137/080725891. Retrieved 22 Apr 2021. https://www.researchgate.net/publication/220124333 ↩

  41. Bush, Jacqueline (10 Jun 2011). "University of California, Santa Barbara Senior Thesis: Bregman Algorithms" (PDF). University of California Santa Barbara. Archived (PDF) from the original on 2016-11-30. Retrieved 16 Apr 2021. https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf ↩

  42. Goldstein, Tom; Osher, Stanley (2 Jun 2008). "The Split Bregman Method for L1-Regularized Problems". SIAM J. Imaging Sci. 2 (2): 323–343. doi:10.1137/080725891. Retrieved 22 Apr 2021. https://www.researchgate.net/publication/220124333 ↩

  43. Xiong, Kai; Zhao, Guanghui; Shi, Guangming; Wang, Yingbin (2019-09-12). "A Convex Optimization Algorithm for Compressed Sensing in a Complex Domain: The Complex-Valued Split Bregman Method". Sensors. 19 (20) (published 18 Oct 2019): 4540. Bibcode:2019Senso..19.4540X. doi:10.3390/s19204540. PMC 6832202. PMID 31635423. https://www.researchgate.net/publication/336665179 ↩