Método Bregman

El método de Bregman es un algoritmo iterativo para resolver ciertos problemas de optimización convexa que implican regularización . ^{[ 1 ]} La versión original se debe a Lev M. Bregman , quien la publicó en 1967. ^{[ 2 ]}

El algoritmo es un método de acción por filas que accede a las funciones de restricción una por una y el método es particularmente adecuado para grandes problemas de optimización donde las restricciones se pueden enumerar de manera eficiente . El algoritmo funciona particularmente bien para regularizadores como el${\displaystyle \ell _{1}}$norma, donde converge muy rápidamente debido a un efecto de cancelación de errores. ^{[ 3 ]}

Para poder utilizar el método de Bregman, uno debe plantear el problema de interés como encontrar${\displaystyle \min _{u}J(u)+f(u)}$, dónde${\displaystyle J}$es una función regularizadora como${\displaystyle \ell _{1}}$. ^{[ 3 ]}

La distancia de Bregman se define como${\displaystyle D^{p}(u,v):=J(u)-(J(v)+\langle p,uv\rangle )}$dónde${\displaystyle p}$pertenece al subgradiente de${\displaystyle J}$en${\displaystyle u}$(que hemos denominado${\displaystyle \partial J(u)}$). ^{[ 3 ] [ 4 ]} Se realiza la iteración${\displaystyle u_{k+1}:=\min _{u}(\alpha D(u,u_{k})+f(u))}$, con${\displaystyle \alpha }$una constante que debe ser elegida por el usuario (y la minimización realizada por un algoritmo de optimización convexa ordinario), ^{[ 3 ]} o${\displaystyle u_{k+1}:=\min _{u}(D^{p_{k}}(u,u_{k})+f(u))}$, con${\displaystyle p_{k}}$elegido cada vez para ser miembro de${\displaystyle \partial J(u_{k})}$. ^{[ 4 ]}

El algoritmo comienza con un par de variables primal y dual. A continuación, para cada restricción, se realiza una proyección generalizada sobre su conjunto factible, actualizando tanto la variable dual de la restricción como todas las variables primal cuyos coeficientes en el gradiente de las funciones de restricción sean distintos de cero. Si la función objetivo es estrictamente convexa y todas las funciones de restricción son convexas, el límite de esta proyección iterativa converge al par primal-dual óptimo.

En el caso de un problema de tipo búsqueda de base${\displaystyle \min _{x:Ax=b}(|x|_{1}+{\frac {1}{2\alpha }}|x|_{2}^{2})}$El método de Bregman es equivalente al descenso de gradiente ordinario en el problema dual.${\displaystyle \min _{y}(-b^{t}y+{\frac {\alpha }{2}}|A^{t}y-{\text{Proj}}_{[-1,1]^{n}}(A^{t}y)|^{2})}$. ^{[ 5 ]} En este caso también se produce un efecto de regularización exacto; si${\displaystyle \alpha }$supera cierto umbral, el valor óptimo de${\displaystyle x}$es precisamente la solución óptima de${\displaystyle \min _{x:Ax=b}|x|_{1}}$. ^{[ 3 ] [ 5 ]}

El método Bregman o sus generalizaciones se pueden aplicar a:

• Desenfoque o eliminación de ruido de la imagen ^{[ 3 ]} (incluida la eliminación de ruido de variación total ^{[ 4 ]} )
• Reconstrucción de imágenes de RM ^{[ 3 ]}
• Imágenes por resonancia magnética ^{[ 1 ] [ 6 ]}
• Radar ^{[ 1 ]}
• Imágenes hiperespectrales ^{[ 7 ]}
• Detección comprimida ^{[ 5 ]}
• Desviaciones absolutas mínimas o${\displaystyle \ell _{1}}$-regresión lineal regularizada ^{[ 8 ]}
• Selección de covarianza (aprendizaje de una matriz de covarianza dispersa) ^{[ 8 ]}
• Completar la matriz ^{[ 9 ]}
• Minimización del riesgo estructural ^{[ 8 ]}

El método tiene vínculos con el método de multiplicadores y el método de ascenso dual (a través del llamado método de direcciones alternas de Bregman de multiplicadores , ^{[ 10 ] [ 7 ]} generalizando el método de direcciones alternas de multiplicadores ^{[ 8 ]} ) y existen múltiples generalizaciones.

Una desventaja del método es que solo se puede demostrar su convergencia si la función objetivo es estrictamente convexa. En caso de que esto no se pueda garantizar, como en el caso de programas lineales o programas cuadráticos no estrictamente convexos, se han desarrollado métodos adicionales, como los métodos de gradiente proximal . En el caso del modelo de Rudin-Osher-Fatemi para la eliminación de ruido en imágenes , el método de Bregman converge de forma demostrable. ^{[ 11 ]}

Algunas generalizaciones del método Bregman incluyen:

• Método del espacio de escala inversa ^{[ 3 ]}
• Bregman linealizado ^{[ 3 ]}
• Logística Bregman ^{[ 3 ]}
• Bregman dividido ^{[ 3 ]}