The chapter focuses on two families of distance-like functions based on ?-divergences and Bregman distances. The approach presented below recovers many results attributed to clustering with squared Euclidean distance. Centroids computation is the basic problem associated with applications k-means clustering with various distance-like functions. Surprisingly, it turns out that in many cases optimization Problem 2.1.1 with divergences admits simple solutions.

To generate the families of distance-like functions we shall need convex, proper functions with nonempty effective domain. In addition often the functions will be required to be lower semicontinuous (see Chapter 10.3 for appropriate definitions).

8.1. Bregman Distance

Let ? : R ⁿ ?( ? ? , + ?] be a closed proper convex function. Suppose that ? is continuously differentiable on int(dom ?) ? . The Bregman distance (also called Bregman divergence ) D _? : dom ? int(dom ?) ? R ₊ is defined by

where ? ? is the gradient of ?.

This function measures the convexity of ?, i.e. D _?( x , y) ? 0 if and only if the gradient inequality for ? holds, that is, if and only if ? is convex. With ? strictly convex one has D _?( x , y) ? 0 and D _?( x , y) = 0 iff x = y (See Figure 8.1).

Figure 8.1: Bregman...