# Bregman distance

Given a convex closed set $C \subset \mathbf R ^ {n}$ with non-empty interior $C ^ {o}$ and a Bregman function $f$ with zone $C$, the Bregman distance ${D _ {f} } : {C \times C ^ {o} } \rightarrow \mathbf R$ is defined as:

$$D _ {f} ( x,y ) = f ( x ) - f ( y ) - \left \langle {\nabla f ( y ) ,x - y } \right \rangle .$$

Bregman distances were introduced in [a1]. For several examples of Bregman distances for relevant sets $C$, see Bregman function. It follows easily from the properties of Bregman functions that $D _ {f} ( x,y ) \geq 0$ for all $x \in C$ and all $y \in C ^ {o}$, that $D _ {f} ( x,y ) = 0$ if and only if $x = y$ and that $D _ {f} ( \cdot,y )$ is a convex function (cf. also convex function (of a real variable)) for all $y \in C ^ {o}$. In general, $D _ {f}$ does not satisfy the triangle inequality, it is not symmetric (i.e. it is not true that $D _ {f} ( x,y ) = D _ {f} ( y,x )$ for all $x$, $y$) and $D _ {f} ( x, \cdot )$ is not convex. If $C = \mathbf R ^ {n}$ and either $D _ {f}$ is symmetric or $D _ {f} ( x, \cdot )$ is convex for all $x \in C$, then $f$ is a quadratic function and $D _ {f}$ is the square of an elliptic norm. A basic property of Bregman distances, which follows easily from the definition, is the following:

$$D _ {f} ( x,y ) + D _ {f} ( y,z ) - D _ {f} ( x,z ) =$$

$$= \left \langle {\nabla f ( z ) - \nabla f ( y ) ,x - y } \right \rangle$$

for all $x \in C$, and all $y,z \in C ^ {o}$. Given a closed convex set $L \subset \mathbf R ^ {n}$ such that $L \cap C \neq \emptyset$, the Bregman projection onto $L$, ${P _ {L} ^ {f} } : {C ^ {o} } \rightarrow L$, is defined as

$$P _ {L} ^ {f} ( z ) = { \mathop{\rm argmin} } \left \{ {D _ {f} ( x,z ) } : {x \in L \cap C } \right \} .$$

The properties of Bregman distances ensure existence and uniqueness of $P _ {L} ^ {f} ( z )$ for all $z \in C ^ {o}$. Given closed convex sets $L _ {1} \dots L _ {m}$ such that $P _ {L _ {i} } ^ {f} ( z ) \in C ^ {o}$ for all $z \in C ^ {o}$ and all $i$( such sets are said to be zones consistent with $f$), it is interesting to consider a sequence of successive Bregman projections onto the convex sets $L _ {i}$, i.e. the sequence $\{ x ^ {k} \}$ with $x ^ {0} \in C ^ {o}$ and iterative formula given by

$$x ^ {k + 1 } = P _ {L _ {i ( k ) } } ^ {f} ( x ^ {k} ) ,$$

where $i ( k )$ is the index of the convex set used in the $k$ th iteration (for instance cyclically, i.e. $i ( k ) = k { \mathop{\rm mod} } m$). This algorithm, called Bregman's method, converges to a point in $L = \cap _ {i = 1 } ^ {m} L _ {i}$ if $L$ is non-empty (see [a1]). It has been proved in [a1] that if all the sets $L _ {i}$ are hyperplanes, then the limit of the sequence $\{ x ^ {k} \}$ is also the unique solution of ${ \mathop{\rm min} } f$, subject to $x \in \cap _ {i = 1 } ^ {m} L _ {i}$. This property also holds for an underrelaxed version of the method, of the type

$$x ^ {k + 1 } = P _ {H _ {k} } ^ {f} ( k ) ,$$

where $H _ {k}$ is a hyperplane parallel to $L _ {i ( k ) }$ and lying between $x ^ {k}$ and $L _ {i ( k ) }$( see [a3]). Under suitable modifications in the definition of the hyperplane $H _ {k}$, the method has been extended to the case of minimization of $f$ subject to linear inequalities and linear interval constraints (see [a2], [a5]). The entropy maximization method known as MART (multiplicative algebraic reconstruction technique, see [a4]) is a particular case of Bregman's method with $C = \mathbf R _ {+} ^ {n}$( the non-negative orthant of $\mathbf R ^ {n}$) and $f ( x ) = \sum _ {j = 1 } ^ {n} x _ {j} { \mathop{\rm log} } x _ {j}$, under a specific underrelaxation strategy.

Bregman distances have also been used to generate generalized proximal point methods for convex optimization and variational inequalities (cf. Proximal point methods in mathematical programming).

How to Cite This Entry:
Bregman distance. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bregman_distance&oldid=46161
This article was adapted from an original article by A.N. Iusem (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article