License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.39
URN: urn:nbn:de:0030-drops-71985
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7198/
Go to the corresponding LIPIcs Volume Portal

Edelsbrunner, Herbert ; Wagner, Hubert

Topological Data Analysis with Bregman Divergences

pdf-format:
LIPIcs-SoCG-2017-39.pdf (0.9 MB)

Abstract

We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback-Leibler divergence, which is commonly used for comparing text and images, and the Itakura-Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized Cech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized Cech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory.

BibTeX - Entry

@InProceedings{edelsbrunner_et_al:LIPIcs:2017:7198,
  author =	{Herbert Edelsbrunner and Hubert Wagner},
  title =	{{Topological Data Analysis with Bregman Divergences}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7198},
  URN =		{urn:nbn:de:0030-drops-71985},
  doi =		{10.4230/LIPIcs.SoCG.2017.39},
  annote =	{Keywords: Topological data analysis, Bregman divergences, persistent homology, proximity complexes, algorithms}
}

Keywords: Topological data analysis, Bregman divergences, persistent homology, proximity complexes, algorithms
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI