Bregman sided and symmetrized centroids
(Kullback-Leibler entropic means of exponential families)
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)
Bregman means (centroids) for various divergences:
Entropic means (centroids) of image histograms:
You can try the Java Applet for SKL centroids on your own images too here
Entropic means (centroids) of multivariate normals:
Java Applets for entropic centroids of bivariate normals
April-December 2007, (c) Frank Nielsen.