Total Jensen divergences: Definition, properties and clustering

Frank Nielsen, Richard Nock

Introduction

In many scientific fields, such as medical imaging (specifically Diffusion Tensor MRI), data is represented as complex geometric objects like 3D ellipsoids. To compare these objects, researchers use "divergences"—mathematical measures of dissimilarity. However, standard measures like the Jensen divergence or Bregman divergence are "coordinate-dependent." They typically measure the "vertical" distance between a point and a curve. If you rotate your data's coordinate system, this vertical distance changes, which is a major drawback when the orientation of the data shouldn't affect the underlying similarity. This paper introduces "total" Jensen divergences, a new family of distance measures that are naturally invariant to coordinate rotations.

Defining Total Jensen Divergence

The authors define the total Jensen divergence (tJ) through a clever geometric shift. Instead of measuring the vertical gap between a convex function and its chord (the line segment connecting two points on the function), they measure the unique orthogonal projection onto that chord.

Figure 2: The total Jensen divergence is defined as the unique orthogonal projection of a point on the function graph onto the line passing through two other points. This construction ensures rotational invariance.

Key technical contributions include the derivation of Conformal Factors, showing that a total Jensen divergence is essentially an ordinary Jensen divergence multiplied by a scaling term that compensates for rotation.

Rotational Invariance and Clustering

By moving from "vertical" distances to orthogonal projections, the authors bake rotational invariance directly into the geometry of the divergence. This ensures that the similarity measure remains the same regardless of how the coordinate system is rotated, a property illustrated by comparing the divergence across different coordinate frames.

Figure 4: Comparison of the total Jensen divergence construction in standard (left) and rotated (right) coordinate systems, demonstrating its inherent rotational invariance.

One of the most practical insights is the application to clustering. Since these divergences don't have simple "average" centers (centroids), the authors propose a two-stage iterative algorithm using the Convex-Concave Procedure (CCCP) to approximate them. Furthermore, they prove that the popular $k$-means++ initialization strategy—which picks initial cluster centers far apart from each other—still works for total Jensen divergences, providing a constant-factor $O(\log k)$ approximation to the optimal clustering.

Key Results and Insights

  • Closed-form Conformal Factors: The authors successfully derived closed-form expressions for the scaling factors of several popular divergences (Shannon, Burg, etc.) when converted to their "total" forms.
  • The Metric Property is Fragile: While the square root of the standard Jensen-Shannon divergence is a metric, the authors show that adding the "total" (rotation-invariant) property destroys this metric property.
  • Robustness: The paper uses "influence functions" to show that the robustness of a cluster center to outliers depends heavily on the underlying convex function. For instance, the total Jensen-Burg divergence is robust, while the total Jensen-Shannon is not.

Limitations and Future Work

The authors acknowledge several open challenges, including proving whether total Jensen centroids are always unique for any given multivariate generator and whether they are robust for all possible smooth convex generators. Additionally, because there is no closed-form solution for the centroids, these divergences are more computationally demanding than standard Euclidean or Bregman $k$-means.

Summary updated

Abstract

We present a novel class of divergences induced by a smooth convex function called total Jensen divergences that are invariant by construction to rotations, a feature inducing a conformal factor on ordinary Jensen divergences. We analyze the relationships between this novel class of total Jensen divergences and the total Bregman divergences. We then define total Jensen centroids, analyze their robustness, and prove that the k-means++ initialization that bypasses explicit centroid computations is good enough in practice to guarantee probabilistically a constant approximation factor to the optimal k-means clustering.
BibTeX
@inproceedings{nielsen2015total,
  author = {Frank Nielsen and Richard Nock},
  title = {{Total Jensen divergences: Definition, properties and clustering}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2015},
  doi = {10.1109/icassp.2015.7178324},
}
Figure