Bregmans metod

Bregmanmetoden är en iterativ algoritm för att lösa vissa konvexa optimeringsproblem som involverar regularisering . Originalversionen beror på Lev M. Bregman , som publicerade den 1967.

Algoritmen är en radåtgärdsmetod som får åtkomst till begränsningsfunktioner en efter en och metoden är särskilt lämpad för stora optimeringsproblem där begränsningar effektivt kan räknas upp [ . Algoritmen fungerar särskilt bra för regularizers som $\ell _{1}$ -normen, där den konvergerar mycket snabbt på grund av en felavbrytande effekt.

Algoritm

För att kunna använda Bregmanmetoden måste man formulera problemet av intresse som att hitta $\min _{u}J(u)+f(u)$ , där $J$ är en regulariserande funktion såsom $\ell _{1}$ .

Bregmanavståndet definieras som $:=J (u)-(J(v)+\langle p,uv\rangle )}$ ) där $p$ tillhör subdifferentialen för J $\displaystyle J}$ vid $u$ (som vi betecknade $\partial J(u)$ ). Man utför iterationen $u_{k+1}:=\min _{u}(\alpha D(u ,u_{k})+f(u))$ , med $\alpha$ en konstant som ska väljas av användaren (och minimeringen som utförs av en vanlig konvex optimeringsalgoritm), eller $u_{k+1}:=\min _{u}(D^{p_{k}}(u,u_{k })+f(u))$ , med $p_{k}$ vald varje gång för att vara medlem av $\partial J(u_{k})$ .

Algoritmen börjar med ett par primala och dubbla variabler. Sedan, för varje begränsning , utförs en generaliserad projektion på dess möjliga uppsättning, som uppdaterar både begränsningens dubbla variabel och alla primala variabler för vilka det finns koefficienter som inte är noll i gradienten för begränsningsfunktioner. Om objektivet är strikt konvext och alla begränsningsfunktioner är konvexa, konvergerar gränsen för denna iterativa projektion till det optimala primala dubbelparet.

I fallet med ett problem av typen base pursuit ${\displaystyle \min _{x:Ax=b}(|x|_ {1}+{\frac {1}{2\alpha }}|x|_{2}^{2})} ,$ Bregman-metoden är ekvivalent med vanlig gradientnedstigning på det dubbla problemet $\min _{y}(-b^{t}y+{\frac {\alpha }{2 }}|A^{t}y-{\text{Proj}}_{[-1,1]^{n}}(A^{t}y)|^{2})$ . En exakt regulariseringsliknande effekt uppträder också i detta fall; om $\alpha$ överskrider en viss tröskel, är det optimala värdet för $x$ exakt den optimala lösningen av $\min _{x:Ax=b}|x|_{1}$ .

Ansökningar

Bregmanmetoden eller dess generaliseringar kan tillämpas på:

• Bildsuddare eller försvagande av brus (inklusive total variationsnedsättning )
• MR-bild rekonstruktion
• Magnetisk resonanstomografi
• Radar
• Hyperspektral avbildning
• Komprimerad avkänning
• Minsta absoluta avvikelser eller $\ell _{1}$ -regulerad linjär regression
• Kovariansval (lära sig en gles kovariansmatris)
• Matriskomplettering
• Strukturell riskminimering

Generaliseringar och nackdelar

Metoden har kopplingar till metoden för multiplikatorer och dubbel uppstigningsmetoden (genom den så kallade Bregman alternerande riktningsmetoden för multiplikatorer , generalisering av den alternerande riktningsmetoden för multiplikatorer ) och det finns flera generaliseringar.

En nackdel med metoden är att den endast bevisligen är konvergent om den objektiva funktionen är strikt konvex. Om detta inte kan säkerställas, som för linjära program eller icke strikt konvexa kvadratiska program, har ytterligare metoder som proximala gradientmetoder utvecklats. I fallet med Rudin-Osher-Fatemi-modellen av bildnedsättning [ , konvergerar Bregman-metoden bevisligen.

Några generaliseringar av Bregman-metoden inkluderar:

• Omvänd skala rymdmetod
• Linjäriserad Bregman
• Logistic Bregman
• Split Bregman

Linjäriserad Bregman

I den lineariserade Bregman-metoden linjäriserar man de mellanliggande objektivfunktionerna $D^{p}(u,u_{k})+f(u)$ genom att ersätta andra termen med $f(u_{k})+\langle f'(u_{k}),u-u_{k} \rangle$ (som approximerar den andra termen nära $u_{k}$ ) och lägga till strafftermen ${\frac {1}{2\delta }}|u-u_{k}|_{2}^{2}$ för en konstant $\delta$ . Resultatet är mycket mer beräkningsmässigt hanteringsbart, särskilt i problem av typen basjakt . I fallet med ett generiskt efterföljande problem ${\displaystyle \min \mu |u|_{1}+{\frac {1}{2}}|Au-f|_{2}^{2}} , man kan$ uttrycka iterationen som ${\displaystyle v_{k+1}:=v_{k} +A^{t}(f-Au_{k}),u_{k+1,i}:=\delta ~{\text{shrink}}(v_{k,i},\mu )} för varje$ komponent $i$ , där vi definierar ${\text{shrink}}(y,a):={\begin{cases}ya,&y\in (a,\infty )\\0,&y\in [-a,a]\ \y+a,&y\in (-\infty ,-a)\end{cases}}$ .

Ibland, när man kör Linearized Bregman-metoden, finns det perioder av "stagnation" där den återstående [ är nästan konstant. För att lindra detta problem kan man använda den Lineariserade Bregman-metoden med kicking , där man i huvudsak upptäcker början av en stagnationsperiod, sedan förutsäger och hoppar till slutet av den.

Eftersom Linearized Bregman är matematiskt likvärdig med gradientnedstigning, kan den accelereras med metoder för att accelerera gradientnedstigning, såsom linjesökning, L-BGFS , Barzilai-Borwein-steg eller Nesterov-metoden; den sista har föreslagits som den accelererade linjäriserade Bregman-metoden .

Split Bregman

Split Bregman-metoden löser problem av formen ${\displaystyle \min _{u}|\Phi (u)|_{1}+H(u)} ,$ där $\Phi$ och $H$ båda är konvex, särskilt problem av formen $\min _{u}|\Phi u|_{1}+|Ku-f|^{2}$ . Vi börjar med att skriva om det som det begränsade optimeringsproblemet ${\displaystyle \min _{u:d=\Phi (u)}|d|_{1}+H(u)} ,$ slappna sedan av till $\min _{u,d}|d|_{1}+H(u)+{\frac {\lambda }{2}}|d-\Phi (u)|_{2} ^{2}$ där $\lambda$ är en konstant. Genom att definiera ${\displaystyle J(u,d):=|d|+H(u)} ,$ man reducerar problemet till ett som kan lösas med den vanliga Bregman-algoritmen.

Split Bregman - metoden har generaliserats till optimering över komplexa tal med Wirtinger - derivator .