Bregman distances and variational source rates

Let $X$ be a real Banach space and let $X^{\ast }$ be its continuous real dual. The dual pairing is evaluation, written $⟨\xi ,x{⟩}_{X^{\ast },X}:=\xi (x)$ for $\xi \in X^{\ast }$ and $x\in X$. Let $R:X\to (-\mathrm{\infty },+\mathrm{\infty }]$ be a proper convex functional: $R$ never takes the value $-\mathrm{\infty }$, its effective domain $\mathrm{dom}R:=\{x\in X:R(x)<+\mathrm{\infty }\}$ is nonempty, and $R((1-t)x+tz)\le (1-t)R(x)+tR(z)$ for $x,z\in X$ and $t\in [0,1]$, with $0\cdot (+\mathrm{\infty }):=0$ for this convex-combination formula. For $x\in \mathrm{dom}R$, its subdifferential is

$\mathrm{\partial }R(x):=\{\xi \in X^{\ast }:R(z)\ge R(x)+⟨\xi ,z-x{⟩}_{X^{\ast },X}\text{ for every }z\in X\}\mathrm{.}$

An element of $\mathrm{\partial }R(x)$ is a subgradient of $R$ at $x$. Set $\mathrm{\partial }R(x):=\mathrm{\varnothing }$ when $x\mathrm{\notin }\mathrm{dom}R$. The subdifferential may be empty at a point of $\mathrm{dom}R$; no nonemptiness assertion is part of this definition.

Real Banach spaces

The continuous dual and evaluation pairing

Convex extended-real functionals

Properness and effective domain

Barbara Kaltenbacher, Convergence rates under a range invariance condition with application to electrical impedance tomography, §1

Jonathan M. Borwein and Jon D. Vanderwerff, Convex Functions: Constructions, Characterizations and Counterexamples, Chapter 4

Let $\psi :[0,\mathrm{\infty })\to [0,\mathrm{\infty })$ be continuous, nondecreasing, concave, and satisfy $\psi (0)=0$. Extend $g=-\psi$ to $\mathbb{R}$ by $g(s)=+\mathrm{\infty }$ for $s<0$, and define $H(q):=g^{\ast }(-q)={\sup }_{s\ge 0}(\psi (s)-qs)$ for $q>0$, assuming the displayed suprema below are finite. For $c_1,c_2,C_3,\alpha >0$ and $d,r,e\ge 0$, if

$c_{1}r+c_2\alpha e\le d+\alpha \psi (C_{3}r),$

then

$e\le \frac{1}{c_2}(\frac{d}{\alpha }+H\text{\hspace{0.17em}⁣}\left(\frac{c_1}{C_3\alpha }\right)),r\le \frac{2}{c_1}(d+\alpha H\text{\hspace{0.17em}⁣}\left(\frac{c_1}{2C_3\alpha }\right))\mathrm{.}$

Barbara Kaltenbacher, Convergence rates under a range invariance condition with application to electrical impedance tomography, Lemma 2 and Appendix A.1

Frederic Weidling, Variational Source Conditions and Conditional Stability Estimates for Inverse Problems in PDEs, Theorem 2.20

Let $X$ be a real Banach space, let $R:X\to (-\mathrm{\infty },+\mathrm{\infty }]$ be proper and convex, and define its Fenchel conjugate $R^{\ast }:X^{\ast }\to (-\mathrm{\infty },+\mathrm{\infty }]$ by $R^{\ast }(\xi ):={\sup }_{z\in X}(⟨\xi ,z{⟩}_{X^{\ast },X}-R(z))$. For every $x\in \mathrm{dom}R$ and $\xi \in X^{\ast }$, the Fenchel–Young inequality and its equality characterization are

$R(x)+R^{\ast }(\xi )\ge ⟨\xi ,x{⟩}_{X^{\ast },X},R(x)+R^{\ast }(\xi )=⟨\xi ,x{⟩}_{X^{\ast },X}⟺\xi \in \mathrm{\partial }R(x)\mathrm{.}$

Jonathan M. Borwein and Jon D. Vanderwerff, Convex Functions: Constructions, Characterizations and Counterexamples, Proposition 4.4.1(a)

Let $X$ be a real Banach space, let $R:X\to (-\mathrm{\infty },+\mathrm{\infty }]$ be proper and convex, choose $x^{†}\in \mathrm{dom}R$, and choose ${\xi }^{†}\in \mathrm{\partial }R(x^{†})$. For $x\in \mathrm{dom}R$, the Bregman distance generated by ${\xi }^{†}$ from the reference point $x^{†}$ to $x$ is

$D_R^{{\xi }^{†}}(x,x^{†}):=R(x)-R(x^{†})-⟨{\xi }^{†},x-x^{†}{⟩}_{X^{\ast },X}\mathrm{.}$

The subgradient inequality makes this quantity nonnegative, and $D_R^{{\xi }^{†}}(x^{†},x^{†})=0$. The definition fixes the orientation: the first argument is the comparison point and the second is the reference point carrying the chosen subgradient.

Banach subgradients and dual pairings

Fenchel–Young equality and inequality

Barbara Kaltenbacher, Convergence rates under a range invariance condition with application to electrical impedance tomography, equation (1.25)

Frederic Weidling, Variational Source Conditions and Conditional Stability Estimates for Inverse Problems in PDEs, Chapter 2

Let $X,Y$ be real Banach spaces, let $F:D(F)\subseteq X\to Y$, let $x^{†}\in D(F)$ with exact datum $y=F(x^{†})$, and let $R:X\to (-\mathrm{\infty },+\mathrm{\infty }]$ be proper and convex with $x^{†}\in \mathrm{dom}R$. Fix ${\xi }^{†}\in \mathrm{\partial }R(x^{†})$, an exponent $1\le p<\mathrm{\infty }$, a continuous nondecreasing concave function $\psi :[0,\mathrm{\infty })\to [0,\mathrm{\infty })$ with $\psi (0)=0$ and $\psi (t)>0$ for $t>0$, a coefficient $0\le \beta <1$, and a level $R_0\ge R(x^{†})$. The variational source condition with these data holds on the named regularizer sublevel $L_{R_0}:=\{x\in D(F):R(x)\le R_0\}$ when

$-⟨{\xi }^{†},x-x^{†}{⟩}_{X^{\ast },X}\le \beta D_R^{{\xi }^{†}}(x,x^{†})+\psi \text{\hspace{0.17em}⁣}(\mathrm{\parallel }F(x)-F(x^{†}){\mathrm{\parallel }}_Y^p)(x\in L_{R_0})\mathrm{.}$

The condition is an assumption on the selected subgradient and the stated sublevel; it makes no assertion that a subgradient exists at every point or that a regularized minimizer exists.

Banach subgradients and dual pairings

Bregman distance orientation

Christian Clason, Regularization of Inverse Problems, equation (10.17)

Frederic Weidling, Variational Source Conditions and Conditional Stability Estimates for Inverse Problems in PDEs, equations (2.22) and (2.26)

Barbara Kaltenbacher, Convergence rates under a range invariance condition with application to electrical impedance tomography, equations (1.28)–(1.31)

Let $X,Y$ be real Banach spaces, $D(F)\subseteq X$, and $F:D(F)\to Y$. Let $R:X\to (-\mathrm{\infty },+\mathrm{\infty }]$ be proper and convex, let $x^{†}\in D(F)\cap \mathrm{dom}R$, set $y=F(x^{†})$, and choose ${\xi }^{†}\in \mathrm{\partial }R(x^{†})$. Fix $1\le p<\mathrm{\infty }$, $0\le \beta <1$, and a level $R_0>R(x^{†})$. Let $\psi :[0,\mathrm{\infty })\to [0,\mathrm{\infty })$ be continuous, nondecreasing and concave, with $\psi (0)=0$ and $\psi (t)>0$ for $t>0$, and assume the variational source inequality

$-⟨{\xi }^{†},x-x^{†}{⟩}_{X^{\ast },X}\le \beta D_R^{{\xi }^{†}}(x,x^{†})+\psi \text{\hspace{0.17em}⁣}(\mathrm{\parallel }F(x)-F(x^{†}){\mathrm{\parallel }}_Y^p)(x\in L_{R_0}:=\{x\in D(F):R(x)\le R_0\}),$

where $D_R^{{\xi }^{†}}(x,x^{†}):=R(x)-R(x^{†})-⟨{\xi }^{†},x-x^{†}{⟩}_{X^{\ast },X}$. Extend $-\psi$ by $+\mathrm{\infty }$ on negative arguments and write $H(q):=(-\psi {)}^{\ast }(-q)={\sup }_{s\ge 0}(\psi (s)-qs)$; assume $H(q)$ is finite for sufficiently large $q$ and $H(q)\to 0$ as $q\to \mathrm{\infty }$. For sufficiently small noise levels $\delta >0$ and data $y^{\delta }\in Y$ with $\mathrm{\parallel }{y}^{\delta }-y{\mathrm{\parallel }}_Y\le \delta$, define $J_{\alpha }^{\delta }(x):=p^{-1}\mathrm{\parallel }F(x)-y^{\delta }{\mathrm{\parallel }}_Y^p+\alpha R(x)$. Suppose $\alpha =\alpha (\delta )>0$ tends to zero, $0\le {\epsilon }_{\delta }\le C_{\epsilon }{\delta }^p$, and $x_{\alpha }^{\delta ,\epsilon }\in D(F)$ is an ${\epsilon }_{\delta }$-minimizer, meaning $J_{\alpha }^{\delta }(x_{\alpha }^{\delta ,\epsilon })\le {\inf }_{z\in D(F)}{J}_{\alpha }^{\delta }(z)+{\epsilon }_{\delta }$. Set $c_p:=2^{1-p}\mathrm{/}p$ and ${\rho }_{\delta }:=H(c_p\mathrm{/}\alpha (\delta ))$. Assume that for constants $c_{-},c_{+},C_H>0$ independent of $\delta$,

$c_{-}{\delta }^p\le \alpha (\delta ){\rho }_{\delta }\le c_{+}{\delta }^p,H(c_p\mathrm{/}(2\alpha (\delta )))\le C_H{\rho }_{\delta }$

for all sufficiently small $\delta$. Then for all sufficiently small $\delta$, $x_{\alpha }^{\delta ,\epsilon }\in L_{R_0}$ and

$D_R^{{\xi }^{†}}(x_{\alpha }^{\delta ,\epsilon },x^{†})=O({\rho }_{\delta }),\mathrm{\parallel }F(x_{\alpha }^{\delta ,\epsilon })-y^{\delta }{\mathrm{\parallel }}_Y=O(\delta )\mathrm{.}$

If, in addition, $\psi (C_0{\delta }^p)=O({\rho }_{\delta })$ for a fixed $C_0$ such that $T_{\delta }:=\mathrm{\parallel }F(x_{\alpha }^{\delta ,\epsilon })-F(x^{†}){\mathrm{\parallel }}_Y^p\le C_0{\delta }^p$ for all sufficiently small $\delta$, then $\mathrm{\mid }R(x_{\alpha }^{\delta ,\epsilon })-R(x^{†})\mathrm{\mid }=O({\rho }_{\delta })$. If also $D_R^{{\xi }^{†}}(x,x^{†})\ge c_R\mathrm{\parallel }x-x^{†}{\mathrm{\parallel }}_X^s$ on $L_{R_0}$ for constants $c_R,s>0$, then $\mathrm{\parallel }{x}_{\alpha }^{\delta ,\epsilon }-x^{†}{\mathrm{\parallel }}_X^s=O({\rho }_{\delta })$.

In the Hilbert special case, set $p=2$ and suppose $X,Y$ are real Hilbert spaces, $F:U\to Y$ has the real open-domain interface of a nonlinear forward map, $x^{†}$ is an $x_0$-minimum-norm exact solution, $R(x)=\frac{1}{2}\mathrm{\parallel }x-x_0{\mathrm{\parallel }}_X^2$, and the source inequality on a regularizer sublevel contained in $U$ is

$⟨x^{†}-x_0,x^{†}-x{⟩}_X\le {\beta }_1\frac{1}{2}\mathrm{\parallel }x-x^{†}{\mathrm{\parallel }}_X^2+{\beta }_2\mathrm{\parallel }F(x)-F(x^{†}){\mathrm{\parallel }}_Y$

with $0\le {\beta }_1<1$ and ${\beta }_2\ge 0$. For exact global minimizers of the nonlinear Tikhonov functional with $\alpha (\delta )\asymp \delta$, the theorem gives $\mathrm{\parallel }{x}_{\alpha (\delta )}^{\delta }-x^{†}{\mathrm{\parallel }}_X=O(\sqrt{\delta })$ and $\mathrm{\parallel }F(x_{\alpha (\delta )}^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y=O(\delta )$. The assertion is conditional on such a global minimizer being supplied; it does not assert existence or cover local numerical minima.

Christian Clason, Regularization of Inverse Problems, equation (10.17) and Theorem 10.7

Frederic Weidling, Variational Source Conditions and Conditional Stability Estimates for Inverse Problems in PDEs, Theorem 2.20

Barbara Kaltenbacher, Convergence rates under a range invariance condition with application to electrical impedance tomography, Lemma 2 and Theorem 3