Bregman divergence ($D_J^p(u,v)$)

For a convex functional $J$ and $p\in \partial J(v)$, the Bregman divergence isIt is nonnegative but need not be symmetric or satisfy the triangle inequality.

Starting with $u^0=0$ and $p^0=0\in \partial J(0)$, update $p^{k+1}=p^k+K^{\ast }(f-K{u}^{k+1})/\alpha$. The optimality condition makes $p^{k+1}\in \partial J(u^{k+1})$. The iteration replaces a fixed penalty by its Bregman distance from the preceding iterate and accumulates residual information in the dual variable. The first update uses $k=0$.

For a generalized singular vector, exact data $f=\gamma K{u}_{\lambda }$, and fixed $\alpha >0$, a compatible branch of Bregman iteration has $p^k=\min \{k\gamma /\alpha ,\lambda \}{K}^{\ast }K{u}_{\lambda }$ and the displayed $u^k$. Verify these formulas with the subgradient characterization of an absolutely one-homogeneous functional; before activation the dual coefficient remains at most $\lambda$, and after activation it is $\lambda$. The branch reaches $\gamma u_{\lambda }$ at $k_{\ast }=\lceil \alpha \lambda /\gamma \rceil +1$. Every minimizer branch has the same predicted data, since the quadratic data fidelity is strictly convex in $Ku$. Exact recovery of this particular vector for arbitrary branch choices needs uniqueness, for example injectivity of $K$. For $K(x,y)=x$ and $J(x,y)=|x|$, the second coordinate of every minimizer is arbitrary.

For $p_u\in \partial J(u)$ and $p_v\in \partial J(v)$, add the two Bregman distances to get $D_J^{p_v}(u,v)+D_J^{p_u}(v,u)=⟨p_u-p_v,u-v⟩\ge 0$. The choice of subgradients matters. This is generally not a metric: it need not separate points or satisfy a triangle inequality.

Let $K:U\to V$ be a bounded linear operator from a real Banach space to a real Hilbert space, let $J$ be a proper lower-semicontinuous convex function, and let $\alpha >0$ and $\Vert f^{\delta }-K{u}^{†}\Vert \le \delta$. For an existing minimizer of $\Vert Ku-f^{\delta }{\Vert }^2/2+\alpha J(u)$ and a source condition in variational regularization $p^{†}=K^{\ast }w\in \partial J(u^{†})$, let $e=f^{\delta }-K{u}^{†}$ and $q=K(u_{\alpha }-u^{†})$. Its optimality subgradient is $p_{\alpha }=K^{\ast }(f^{\delta }-K{u}_{\alpha })/\alpha$. Then $\alpha D_J^{\mathrm{sym}}=⟨e-\alpha w,q⟩-\Vert q{\Vert }^2\le \Vert e-\alpha w{\Vert }^2/4$. The displayed estimate follows from $\Vert e-\alpha w{\Vert }^2\le 2{\delta }^2+2{\alpha }^2\Vert w{\Vert }^2$.

For $p\in \partial J(v)$, zero Bregman distance means that $J(u)$ equals the supporting affine function $J(v)+⟨p,u-v⟩$. If $J$ is strictly convex, two distinct contact points are impossible: convexity along their segment would be strict, while the subgradient inequality supplies the opposite bound. Thus zero distance then implies $u=v$. Without strict convexity, $J(s)=|s|$, $v=1$, $p=1$ gives zero distance for every $u\ge 0$. These are all on the same supporting face.