Bregman method

In order to be able to use the Bregman method, one must frame the problem of interest as finding $\backslash min\_u\; J(u)\; +\; f(u)$, where $J$ is a regularizing function such as $\backslash ell\_1$.

The Bregman distance is defined as $D^p(u,\; v)\; :=\; J(u)\; -\; (J(v)\; +\; \backslash langle\; p,\; u\; -\; v\backslash rangle)$ where $p$ belongs to the subdifferential of $J$ at $u$ (which we denoted $\backslash partial\; J(u)$).{{Cite web|last=Bush|first=Jacqueline|date=10 Jun 2011|title=University of California, Santa Barbara Senior Thesis: Bregman Algorithms|url=https://web.math.ucsb.edu/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf|url-status=live|access-date=16 Apr 2021|website=University of California Santa Barbara|archive-url=https://web.archive.org/web/20161130150743/http://web.math.ucsb.edu:80/~cgarcia/UGProjects/BregmanAlgorithms_JacquelineBush.pdf |archive-date=2016-11-30 }} One performs the iteration $u\_\{k\; +\; 1\}:=\; \backslash min\_u(\backslash alpha\; D(u,\; u\_k)\; +\; f(u))$, with $\backslash alpha$ a constant to be chosen by the user (and the minimization performed by an ordinary convex optimization algorithm), or $u\_\{k\; +\; 1\}:=\; \backslash min\_u(D^\{p\_k\}(u,\; u\_k)\; +\; f(u))$, with $p\_k$ chosen each time to be a member of $\backslash partial\; J(u\_k)$.

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.{{Citation needed|date=April 2021}}

In the case of a basis pursuit-type problem $\backslash min\_\{x:\; Ax\; =\; b\}(|x|\_1\; +\; \backslash frac\{1\}\{2\backslash alpha\}|x|\_2^2)$, the Bregman method is equivalent to ordinary gradient descent on the dual problem $\backslash min\_y\; (-b^t\; y\; +\; \backslash frac\{\backslash alpha\}\{2\}|A^t\; y\; -\; \backslash text\{Proj\}\_\{[-1,\; 1]^n\}(A^t\; y)|^2)$.{{Cite journal|last=Yin|first=Wotao|date=28 May 2009|title=Analysis and Generalizations of the Linearized Bregman Method|url=ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf|journal=SIAM Journal on Imaging Sciences|volume=3|issue=4|pages=856–877|doi=10.1137/090760350|archive-url=https://web.archive.org/web/20170705134816/ftp://ftp.math.ucla.edu/pub/camreport/cam09-42.pdf|archive-date=2017-07-05|url-status=dead|access-date=16 Apr 2021}} An exact regularization-type effect also occurs in this case; if $\backslash alpha$ exceeds a certain threshold, the optimum value of $x$ is precisely the optimum solution of $\backslash min\_\{x:\; Ax\; =\; b\}|x|\_1$.

The Bregman method or its generalizations can be applied to:

• Image deblurring or denoising (including total variation denoising)
• MR image{{Clarify|date=April 2021}} reconstruction
• Magnetic resonance imaging{{Cite journal|last1=Goldstein|first1=Tom|last2=Osher|first2=Stanley|date=2 Jun 2008|title=The Split Bregman Method for L1-Regularized Problems|url=https://www.researchgate.net/publication/220124333|journal=SIAM J. Imaging Sci.|volume=2|issue=2|pages=323–343|doi=10.1137/080725891|access-date=22 Apr 2021}}
• Radar
• Hyperspectral imaging
• Compressed sensing
• Least absolute deviations or $\backslash ell\_1$-regularized linear regression{{Cite journal|last1=Boyd|first1=Stephen|last2=Parikh|first2=Neal|last3=Chu|first3=Eric|last4=Peleato|first4=Borja|last5=Eckstein|first5=Jonathan|date=19 Nov 2010|title=Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers|journal=Foundations and Trends in Machine Learning|volume=3|pages=1–122|doi=10.1561/2200000016|citeseerx=10.1.1.722.981}}
• Covariance selection (learning a sparse covariance matrix)
• Matrix completion{{Cite journal|last1=Huang|first1=Bo|last2=Ma|first2=Shiqian|last3=Goldfarb|first3=Donald|date=27 Jun 2011|title=Accelerated Linearized Bregman Method|journal=Journal of Scientific Computing|publisher=Plenum Press|publication-date=1 Feb 2013|volume=54|issue=2–3|pages=428–453|doi=10.1007/s10915-012-9592-9|arxiv=1106.5413|s2cid=14781930 |issn=0885-7474}}
• Structural risk minimization

The method has links to the method of multipliers and dual ascent method (through the so-called Bregman alternating direction method of multipliers,{{Cite journal|last1=Wang|first1=Huahua|last2=Banerjee|first2=Arindam|date=13 Jun 2013|title=Bregman alternating direction method of multipliers|journal=NIPS'14: Proceedings of the 27th International Conference on Neural Information Processing Systems|volume=2|pages=2816–2824|arxiv=1306.3203}}{{Cite web|last=Jiang|first=Chunzhi|date=May 2015|title=Comparison of Variable Penalty ADMM with Split Bregman Method on Hyperspectral Imaging Problems|url=https://etda.libraries.psu.edu/files/final_submissions/9702|url-status=live|access-date=20 Apr 2021|archive-url=https://web.archive.org/web/20200323014635/https://etda.libraries.psu.edu/files/final_submissions/9702 |archive-date=2020-03-23 }} generalizing the alternating direction method of multipliers) 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.{{Citation needed|date=April 2021}} In the case of the Rudin-Osher-Fatemi model of image denoising{{Clarify|date=April 2021}}, the Bregman method provably converges.{{Cite journal|last=Jia|first=Rong-Qing|date=3 Oct 2008|title=Convergence analysis of the Bregman method for the variational model of image denoising|url=https://sites.ualberta.ca/~rjia/Paper06-10/JZZ09.pdf|journal=Applied and Computational Harmonic Analysis|publication-date=Nov 2009|volume=27|issue=3|pages=367–379|doi=10.1016/j.acha.2009.05.002|access-date=22 Apr 2021|doi-access=free}}

Some generalizations of the Bregman method include:

• Inverse scale space method{{Clarify|date=April 2021}}
• Linearized Bregman
• Logistic Bregman
• Split Bregman

In the Linearized Bregman method, one linearizes the intermediate objective functions $D^p(u,\; u\_k)\; +\; f(u)$ by replacing the second term with $f(u\_k)\; +\; \backslash langle\; f\text{'}(u\_k),\; u\; -\; u\_k\backslash rangle$ (which approximates the second term near $u\_k$) and adding the penalty term $\backslash frac\{1\}\{2\backslash delta\}|u\; -\; u\_k|\_2^2$ for a constant $\backslash delta$. The result is much more computationally tractable, especially in basis pursuit-type problems. In the case of a generic basis pursuit problem $\backslash min\; \backslash mu|u|\_1\; +\; \backslash frac\{1\}\{2\}|Au\; -\; f|\_2^2$, one can express the iteration as $v\_\{k\; +\; 1\}\; :=\; v\_k\; +\; A^t(f\; -\; Au\_k),\; u\_\{k\; +\; 1,\; i\}\; :=\; \backslash delta~\backslash text\{shrink\}(v\_\{k,\; i\},\; \backslash mu)$ for each component $i$, where we define .

Sometimes, when running the Linearized Bregman method, there are periods of "stagnation" where the residual{{Clarify|date=April 2021}} 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.

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.

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

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

{{reflist}}

Category:Optimization algorithms and methods

Category:Convex optimization