Bregman left/right and symmetrized centroids | (c) Frank Nielsen, April-November 2007.

Bregman sided and symmetrized centroids

(Kullback-Leibler entropic means of exponential families)

C++ source codes of Veldhuis' approximation and our geodesic-walk methods for computing the symmetrized Kullback-Leibler centroid (J-divergence).
Java Applet for Bregman sided and symmetrized centroids (video, mixed-type bisector rasterized on the GPU).
Applications to finding image centers wrt. the relative entropy. / Java Applets for SKL centroids
Applications to finding the center of multivariate normal distributions. / Java Applets for entropic centroids of bivariate normals

The Euclidean centroid, also called center of mass, is characterized as the unique point that minimizes the average squared distance. We extend the definition of Euclidean centroids to arbitrary Bregman centroids. Bregman divergences are a parameterized family of distortion measures that includes the squared Euclidean distance and various entropic measures such as the Kullback-Leibler divergence (better known as relative entropy). It is known that except for the class of generalized quadratic distance (including Mahalanobis distances), Bregman divergences are asymmetric. Therefore, to define the Bregman centroids, we take into account the argument position in the minimization process. We have shown that:

The right Bregman centroid is independent of the considered Bregman divergence and coincide with the center of mass (Euclidean centroid).
The left Bregman centroid depends on the Bregman divergence and is computed as the generalized mean (f-mean or quasi-arithmetic mean). This shows that Bregman divergences are also in bijection with generalized arithmetic means.
The symmetrized Bregman centroid is obtained as the intersection of the geodesic linking the right/left centroids with the mixed-type bisector of the left/right centroid. (This exact geometric characterization allows us to define a fast numerical algorithm for approaching the symmetrized Bregman centroid).

Watch or download the video, based on a fast C++ implementation using OpenGL(R) and Cg(R). (Here is a still snapshot)
You can also try the Bregman centroid applet below. Points can be moved by dragging them with the mouse. The right centroid (center of mass) is displayed in red. The left centroid in blue, and the symmetrized centroid in magenta. We rasterize the mixed-type bisector in magenta, and show that the symmetrized Bregman centroid is located at the intersection of the geodesic linking the left/right centroids with the mixed-type bisector. (By default, the Bregman divergence is the squared Euclidean distance. Select and try other Bregman divergences)