Topological data analysis with Bregman divergences

DOI10.4230/LIPICS.SOCG.2017.39MaRDI QIDQ4580114zbMATH OpenFDO

Authors

Publication date 13 August 2018

Full work available at URL https://arxiv.org/abs/1607.06274

zbMATH Keywords

algorithmsBregman divergencespersistent homologyproximity complexestopological data analysis

Mathematics Subject Classification ID

Persistent homology and applications, topological data analysis (55N31) Numerical approximation and computational geometry (primarily algorithms) (65D99) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05)

Abstract: Given a finite set in a metric space, the topological analysis generalizes hierarchical clustering using a 1-parameter family of homology groups to quantify connectivity in all dimensions. The connectivity is compactly described by the persistence diagram. One limitation of the current framework is the reliance on metric distances, whereas in many practical applications objects are compared by non-metric dissimilarity measures. 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. These are two members of the broad family of dissimilarities called Bregman divergences. We show that the framework of topological data analysis can be extended to general Bregman divergences, widening the scope of possible applications. 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.

Recommendations

• Topological data analysis in information space
• Topological data analysis
• Convergence rates for persistence diagram estimation in topological data analysis
• Statistical topological data analysis using persistence landscapes
• Bregman Voronoi diagrams

Cited in

(13)

• Random inscribed polytopes have similar radius functions as Poisson-Delaunay mosaics
• Footprints of geodesics in persistent homology
• A functorial Dowker theorem and persistent homology of asymmetric networks
• Topological data analysis of noise: uniform unimodal distributions
• scientific article; zbMATH DE number 7368521 (Why is no real title available?)
• Topological Data Analysis in Information Space.
• Smallest enclosing spheres and Chernoff points in Bregman geometry
• On Geodesic Triangles with Right Angles in a Dually Flat Space
• N-dimensional Data-Dependent Reconstruction Using Topological Changes
• Topological data analysis in information space
• A gradient sampling algorithm for stratified maps with applications to topological data analysis
• Curved representational Bregman divergences and their applications
• Fast Kd-trees for the Kullback-Leibler divergence and other decomposable Bregman divergences

This page was built for publication: Topological data analysis with Bregman divergences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580114)