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.
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.
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