Total Jensen divergences: Definition, Properties and k-Means++ Clustering

Frank Nielsen, Richard Nock

Introduction

In data analysis fields such as medical imaging (e.g., Diffusion Tensor MRI) and shape retrieval, measuring the dissimilarity between data points is a fundamental task. Standard tools like Jensen divergences (including the Jensen-Shannon divergence) are often employed. However, these measures possess a significant geometric limitation: they are defined by the "vertical" distance between a convex function and its chord. Consequently, rotating the coordinate system alters the measured distance, which is undesirable in physical applications where coordinate orientation is arbitrary.

Standard Jensen and Bregman divergences are defined by vertical distances, making them sensitive to coordinate system rotations. Total Bregman divergences (tB) were previously proposed to address this for the Bregman family.

While "Total Bregman Divergences" were developed to provide rotation-invariant alternatives for the Bregman family, this paper introduces Total Jensen Divergences (tJ) to fill the corresponding gap for the Jensen family.

Geometric Construction and Rotation Invariance

The core innovation lies in shifting from a vertical geometric definition to an orthogonal one. Instead of measuring the vertical gap between a point on the graph of a convex function $F$ and the line segment (chord) connecting two points $(p, F(p))$ and $(q, F(q))$, the Total Jensen divergence measures the unique orthogonal projection onto that chord.

By switching from vertical projections ($J'_\alpha$) to orthogonal ones ($tJ'_\alpha$), the divergence becomes a property of the graph's intrinsic geometry, ensuring invariance under rotations of the coordinate axes.

This orthogonal construction ensures that the divergence is a property of the graph's geometry rather than the coordinate axes. Mathematically, the authors demonstrate that a Total Jensen divergence is equivalent to a standard Jensen divergence scaled by a conformal factor $\rho_J(p, q)$. This factor regularizes the divergence, though it is "non-separable," meaning it cannot be decomposed into independent terms for $p$ and $q$.

Centroid Estimation and Clustering

Unlike standard Jensen divergences, Total Jensen centroids do not typically have closed-form solutions. To address this, the authors propose a "doubly iterative" algorithm based on the Convex-Concave Procedure (CCCP). This algorithm is guaranteed to converge to a local optimum when minimizing the average total Jensen distortion.

Furthermore, the paper extends the $k$-means++ "seeding" technique to this new class of divergences. The authors prove that by selecting initial cluster centers from the dataset with probabilities proportional to their divergence from existing centers, one can achieve a constant approximation factor—specifically $O(\log k)$—relative to the optimal clustering potential. This result is significant as it provides theoretical guarantees for clustering performance without requiring the computation of complex centroids during the initialization phase.

Properties and Robustness

A notable finding is that while the square root of the standard Jensen-Shannon divergence is a metric, the Total Jensen-Shannon version does not satisfy the triangle inequality. This indicates that rotation invariance comes at the cost of certain metric properties.

Additionally, the robustness of these measures to outliers depends heavily on the choice of the underlying "generator" function $F$. For instance, the Total Jensen-Burg centroid is robust to outliers, whereas the Total Jensen-Shannon centroid is not. This highlights the importance of selecting an appropriate generator for specific data analysis tasks.

Conclusion

Total Jensen Divergences provide a geometrically sound, rotation-invariant framework for measuring dissimilarity. By combining orthogonal projections with rigorous clustering theory, this work offers a robust alternative to standard measures in fields where coordinate independence is paramount. Future research remains focused on proving the uniqueness of centroids for multivariate generators and establishing universal conditions for outlier robustness.

Summary updated

BibTeX
@inproceedings{nielsen2015total,
  author = {Frank Nielsen and Richard Nock},
  title = {{Total Jensen divergences: Definition, Properties and k-Means++ Clustering}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2015},
  doi = {10.1109/icassp.2015.7178324},
}
Figure