Bregman divergences and triangle inequality

Sreangsu Acharyya, Arindam Banerjee, Daniel Boley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

While Bregman divergences have been used for clustering and embedding problems in recent years, the facts that they are asymmetric and do not satisfy triangle inequality have been a major concern. In this paper, we investigate the relationship between two families of symmetrized Bregman divergences and metrics that satisfy the triangle inequality. The first family can be derived from any well-behaved convex function. The second family generalizes the Jensen-Shannon divergence, and can only be derived from convex functions with certain conditional positive definiteness structure. We interpret the required structure in terms of cumulants of infinitely divisible distributions, and related results in harmonic analysis. We investigate kmeans-type clustering problems using both families of symmetrized divergences, and give efficient algorithms for the same.

Original languageEnglish (US)
Title of host publicationProceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
EditorsJoydeep Ghosh, Zoran Obradovic, Jennifer Dy, Zhi-Hua Zhou, Chandrika Kamath, Srinivasan Parthasarathy
PublisherSiam Society
Pages476-484
Number of pages9
ISBN (Electronic)9781611972627
DOIs
StatePublished - 2013
EventSIAM International Conference on Data Mining, SDM 2013 - Austin, United States
Duration: May 2 2013May 4 2013

Publication series

NameProceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013

Other

OtherSIAM International Conference on Data Mining, SDM 2013
Country/TerritoryUnited States
CityAustin
Period5/2/135/4/13

Bibliographical note

Publisher Copyright:
Copyright © SIAM.

Fingerprint

Dive into the research topics of 'Bregman divergences and triangle inequality'. Together they form a unique fingerprint.

Cite this